Luogu P2397 yyy loves Maths VI (mode)
摩尔投票能通过 \(O(n)\) 的时间，\(O(1)\) 的空间完成主元素判断。该过程可以用某些数据结构进行维护，所以在求众数上有比较大的优势。注意该算法必须保证众数存在，否则最后需要再进行一次 \(O(n)\) 空间的判断无解。
算法流程：
- 遍历所有元素，若此时临时变量里没有元素，则设为该元素。
- 否则和临时变量里的数相消，临时变量的计数减 \(1\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
int n, cnt, a, val;
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;while(n--){cin >> a;if(cnt == 0) val = a;if(val == a) cnt++;else cnt--;}cout << val;return 0;
}
核心思想是将两个不同元素相消，最后剩下的就是主元素。
Leetcode 229 多数元素 II
摩尔投票简单拓展。把摩尔投票的每次删两个不同元素改成每次删三个不同元素即可。具体实现上要维护两个候选值与其计数变量。
最后因为要判断有无解，所以空间复杂度依然是 \(O(n)\) 的。
class Solution {
public:vector<int> majorityElement(vector<int>& nums) {vector<int> ans;const int inf = 0x3f3f3f3f;int val1 = -inf, val2 = -inf, cnt1 = 0, cnt2 = 0;for(auto x : nums){if(val1 == x)cnt1++;else if(val2 == x)cnt2++;else if(cnt1 == 0){val1 = x;cnt1++;}else if(cnt2 == 0){val2 = x;cnt2++;}else{cnt1--;cnt2--;}}cnt1 = cnt2 = 0;for(auto x : nums){if(x == val1) cnt1++;else if(x == val2) cnt2++;}if(cnt1 > nums.size() / 3) ans.push_back(val1);if(cnt2 > nums.size() / 3) ans.push_back(val2);return ans;}
};