多数元素

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

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

这个题目是某年的408原题，之前做的时候用的哈希表,答案好像是摩尔投票法不过当时没看懂😅

摩尔投票法

规定众数的票数是1，非众数的票数是-1.由于众数的数量大于总元素个数的一半所以票数之和一定大于0.

若数组的前a个数票数之和为0，则后n-a个数的票数之和一定大于0，所以众数一定在后n-a个数中。

  • 设置一个候选众数 maj = nums[0]，初始化票数和votes = 0.

  • 遍历数组，对于每一个元素x，若x==maj则votes++。否则votes–

  • 遍历结束后maj即为整个数组的众数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int maj=nums[0],votes=0;
        for(int num:nums){
            if(num==maj) votes++;
            else votes--;
            if(votes==0) {
                maj = num;
                votes=1;
            }
        }
        return maj;
    }
};