数组：数学定理

0169. 多数元素 (opens new window)

题目

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

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

解析

Boyer-Moore 投票算法：每次都找出一对不同的元素，从数组中删除，直到数组为空或只有一种元素。

不难证明，如果存在元素 e 出现频率超过半数，那么数组中最后剩下的就只有 e。

代码实现：使用 ans 记录已遍历元素中出现次数最多的元素，count 记录还未被抵消的数量，当遍历结束 ans 即为数组的众数。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0, ans = -1;
        for (int i = 0; i < nums.size(); i ++) {
            if (count == 0) {
                ans = nums[i];
            }
            if (ans != nums[i]) --count;
            else ++count;
        }
        return ans;
    }
};