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

哈希表

计数就行了

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int, int> m;for(const auto &num : nums){++m[num];}for(const auto &num : nums){if(m[num] > nums.size()/2)  return num;}return 0;}
};

显然空间复杂度为O(n)

摩尔投票法

名字倒很罕见，不思路很简单：

• 维护一个候选众数 res 和它出现次数 cnt。可以初始化res为第一个元素；

• 遍历数组 nums 中的所有元素，对于每个元素 x：
  如果 x 与 res 相等，计数器 cnt 加 1；
  如果 x 与 res 不等，计数器 cnt 减 1(此时需要判断cnt是否为0，如果cnt为0，那就更新res为当前数，并且置cnt为1)。

• 遍历完成后，res 即为整个数组的众数。

贴一个别人对摩尔投票法的理解：

摩尔投票法：核心就是对拼消耗。

玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

class Solution {
public:int majorityElement(vector<int>& nums) {int res = nums[0], cnt = 1;for(const auto &num : nums){if(res != num){--cnt;if(cnt == 0){res = num;++cnt;}}else    ++cnt;  }return res;}
};

空间复杂度O(1)。

排序

可以排序，只有直接返回中间元素即可；

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());return nums[nums.size()/2];}
};

随机挑选

看了官方题解才知道还能这么操作：多数元素 - 多数元素 - 力扣（LeetCode）

class Solution {
public:int majorityElement(vector<int>& nums) {while(true){int res = nums[rand()%nums.size()];int cnt = 0;for(const auto &num : nums){if(res == num)  ++cnt;if(cnt > nums.size()/2)    return res;}}return -1;}
};