剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

思路：采用摩尔投票法。思想为票数正负抵消。时间复杂度为O(n)，空间为O(1)。

简单理解：最坏情况拿众数和其他数一换一，最终剩下的肯定是众数。

具体的证明可以看参考题解。

实现：遍历时，两个数不同则票数-1，两个数相同则票数+1，票数为0时，则更新统计的数字(votes)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        int votes = 0;
        int res = 0;
        for (int num : nums) {
            if (votes == 0) {
                res = num;
            }
            votes += num == res ? 1 : -1;
        }
        // 验证res是否为众数
        int cnt = 0;
        for (int num : nums) {
            cnt += num == res ? 1 : 0;
        }
        return cnt > len / 2 ? res : -1;
    }
}

参考题解