摩尔投票法(高阶打擂) leetcode229. 求众数 II

高阶打擂) leetcode229. 求众数 II"/>

摩尔投票法(高阶打擂) leetcode229. 求众数 II

1.摩尔投票法简介

（1）用途

用于解决查找大小为 n 的整数数组，找出其中所有出现严格大于 ⌊ n/k ⌋ 次的元素。

（2）算法

开k-1个仓库，（严格大于 ⌊ n/k ⌋ 次的元素可能有1~ ⌊ n/k ⌋ 个）

1.如果新来的数本来仓库中有，则仓库存量+1。

2.如果新来的数仓库中没有并且有空的仓库（数的次数为0），则来的新数加入仓库。

3.如果新来的数仓库中没有并且所有仓库都不为空则所有仓库中库存-1。

（3）算法可行性

即严格大于 ⌊ n/k ⌋ 次数是否一定会在仓库中，如果想把n/k的数移除仓库至少需要

（⌊ n/k ⌋+1） * k

2. leetcode229. 求众数 II

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

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

class Solution {
public:vector<int> majorityElement(vector<int>& nums) {vector<int> vc;int c1 = 0, c2 = 0, r1 = INT_MIN, r2 = INT_MIN;for(auto num : nums){if(r1 == num) c1++;else if(r2 == num) c2++;else if(!c1) r1 = num, c1++;else if(!c2) r2 = num, c2++;else c1--, c2--;}c1 = 0, c2 = 0;for(auto num : nums){if(num == r1) c1++;else if(num == r2) c2++;}int n = nums.size();if(c1 > n / 3) vc.push_back(r1);if(c2 > n / 3) vc.push_back(r2);return vc;}
};