[Leetcode 169] 摩尔投票法#

感觉很新奇的算法，记录下来。

题意#

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

思路#

哈希表的方法很简单，但是需要 $O(N)$ 的空间复杂度，那么有什么方法能把这 $O(N)$ 的空间复杂度省下来呢？

我们可以对数组中的数字做一个标记，若数字是多数元素，则标记为 $+1$ ，若不是多数元素， 则标记为 $-1$ 。把所有数字加起来，我们可以认为所有标记的和是大于 $0$ 的。

基于此，我们可以开始遍历数组了。我们需要维护一个标记和 $sum$ 与我们暂时认为是多数元素的数 $x$ 。若标记和为 $0$，我们便可以假设我们假设的多数元素 $x$ 为当前这个数。若之后再次遇到 $x$ ，标记和加一，若不是 $x$，标记和减一。最终返回数 $x$ 即可。

这就相当于把数组切成很多个标记为 $0$ 的分段，而且最后一定会遇到一个标记和大于 $0$ 的分段。因为若在这个区间内 $x$ 的数量和其他数字的数量和相抵消，若这个 $x$ 就是多数元素，多数元素的数量在剩下的区间内仍然是最多的。也就是说我们可以保证抵消不会影响多数元素的结果。因此我们可以通过这个空间复杂度为 $O(1)$，时间复杂度为 $O(N)$ 的算法来解决这个问题。

下面是代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0;
        int sum = 0;
        for (int num : nums) {
            if (sum == 0) {
                x = num;
            }
            if (x == num) {
                sum++;
            } else {
                sum--;
            }
        }
        return x;
    }
};