## 摩尔投票算法 --- ## 算法来历 摩尔投票算法（Boyer-Moore Majority Vote Algorithm）由 Robert S. Boyer 和 J Strother Moore 在 1981 年提出，旨在高效解决序列中多数元素的查找问题。 --- ### 多数元素 多数元素是指在数组中出现次数超过数组长度一半的元素。例如，数组 [3, 2, 3] 中，元素 3 出现 2 次，数组长度为 3，2 > 3/2，所以 3 是多数元素。 --- ## 算法原理 摩尔投票算法的核心在于通过抵消不同元素来找到多数元素。想象一场选举，多数元素如同那个得票超半数的候选人。算法用两个变量记录候选元素和票数，遍历数组时，相同元素票数加 1，不同则减 1。多数元素因出现次数占优，最终票数保持正数，成为候选。 一句话解释：让数组中的不同的数两两进行厮杀，最后剩余的一定是多数元素。 --- ## 代码实现 ```c #include <cstdio> #include <iostream> using namespace std; const int N = 2E6 + 5; int n; int main(void) { ios::sync_with_stdio(0); cin >> n; int cand = 0, hp = 0, t; for (int i = 1; i <= n; i++) { cin >> t; if (hp == 0) { cand = t; hp = 1; } else cand == t ? hp++ : hp--; } cout << cand << endl; return 0; } ``` --- ## 经典题目 [whoj-4524](http://39.99.183.126:8888/p/4524)