题目链接

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

示例

输入：
{1,2,2,2,2,3,4}
输出：
2

解题思路

多数投票问题，可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为 O(N)。
摩尔投票算法是一种在一个元素序列中，查找出现次数最多的元素的算法； (详情查看 补充)

首先将数组中第一个数认为是出现最多的数 major=nums[0]
从第二个位置开始遍历数组，m 为统计出现的次数，将遍历到的元素与 major 比较，如果相等 m+1 ,否则 m-1 , 判断如果 m==0 , 则之前出现的数中没有重复的数字，所以将 major 再指向当前元素， m 重置为1。遍历完成后，找到重复的数字 major
再次遍历数组，获得最多重复数字的次数，进行判断然后返回。

代码

public int MoreThanHalfNum_Solution(int [] nums) {
            int major = nums[0];
            for (int i = 1, m = 1; i < nums.length; i++) {
                m = nums[i] == major ? m + 1 : m - 1;
                if (m == 0) {
                    major = nums[i];
                    m = 1;
                }
            }
            int m = 0;
            for (int val : nums){
                if (val == major){
                    m++;
                }
            }
            return m > nums.length / 2 ? major : 0;
        }

补充：

Boyer-Moore Majority Vote Algorithm
摩尔算法实现

1. 定义两个变量：m存储当前变量到的元素，count为计数器，初始情况下，count=0；
2. 依次遍历数组中的每个元素，当遍历到元素x时，

• 如果count == 0，那么m=x，然后将count=1；
• 如果count != 0，将m与x进行比较，如果相等，count++；如果不等，count—；

1. .处理完后，最后m存储的值就是这个序列中最多的元素；

   public int majorityVote(int[] nums) {
        int m = 0;
        int count = 0;
        for (int i : nums) {
            if (count == 0) {
                m = i;
                count++;
            } else if (i == m) {
                count++;
            } else {
                count--;
            }
        }
        return m;
    }