leetCode-169:Majority Element

问题描述

给定一个数组，数组中有个元素的数量超过数组总数的一半，要求找出该元素。题目链接：点我

样例输入输出

输入：[3,2,3]

输出：3

输入：[2,2,1,1,1,2,2]

输出：2

问题解法

此题比较简单的做法是用 map 存储数字及其出现的次数，然后找出最大次数的元素即是求解的答案。另一种简单的做法是排序，然后返回中位数（因为目标元素出现了至少 n / 2次）。但是这两种解决都不能在 O(1) 的空间复杂度、O(n) 的时间复杂度内求解。

更优化的做法是使用Boyer-Moore 算法：先用 candidate 表示候选的数，用 count 表示当前候选数剩余的数量，遍历数组，如果当前元素和候选数相同，则 count + 1，否则 count - 1，如果 count 为零，则将当前元素赋值给 candidate，遍历结束后，count 值一定大于0，此时 candidate 的值就是求解的值。此算法可以换另一种理解，因为求解的值的数量超过一半，所以剩下的元素和目标元素进行抵扣消极后，目标元素仍然有剩余。代码如下

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            } else {
                if (count == 0) {
                    candidate = num;
                    count = 1;
                } else {
                    count--;
                }
            }
        }

        return candidate;
    }
}

参考资料

多数元素 - 多数元素 - 力扣（LeetCode）