题干

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

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

示例 1：

1
2

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

示例 2：

1
2

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

题解

1. 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N) 。
2. 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
3. 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1) ，为本题的最佳解法。

摩尔投票

设输入数组 nums 的众数为 x ，数组长度为 n 。

推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。

推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。

具体代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int majorityElement(vector<int>& nums) {
    int n, t, tmp=nums[0], cnt=0;
    n=size(nums);
    for(int i=0;i<n;i++)
    {
        t=nums[i];
        if(cnt==0) tmp=t, cnt++;
        else
        {
            if(t==tmp) cnt++;
            else cnt--;
        }
    }
    return(tmp);
}