Leetcode 169. 多数元素

题干

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length

• 1 <= n <= 5 * 10^4

• -10^9 <= nums[i] <= 10^9

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

初见

只能想到空间复杂度为 O(n)的哈希表或者时间复杂度为 O(n\log n)的排序取中值...

优化

Boyer-Moore 投票算法

对于数列 1 1 2 3 1 1 2 ，维护一个和值 sum = 0 ，首先假设候选数字 candidate = 1 ，遍历该数列，每读到候选数字则 sum + 1 ，否则 sum - 1 ，可以发现当再一次出现 sum = 0 时，已读过的数列为 1 1 2 3 ，删去该数列完全不影响众数的判定。对于极端情况如 1 1 2 2 1 1 2 与 1 1 2 2 1 2 2，假设在读到 1 1 2 2 时我们仍不知道众数到底是 1 还是 2 ，可以发现根据剩下的后三位 1 1 2 与 1 2 2 足以判断众数。

class Solution {
    public int majorityElement(int[] nums) {
        int sum = 0, candidate = 0;
        for (int num : nums) {
            if (sum == 0) {
                candidate = num;
            }
            sum += (candidate == num) ? 1 : -1;
        }
        return candidate;
    }
}