摩尔投票算法( Boyer-Moore Voting Algorithm)

 1 class Solution {
 2 public:
 3     vector<int> majorityElement(vector<int>& nums) {
 4         vector<int> ans;
 5         // 分别是候选人a，候选人b，以及a，b的票数
 6         int ca = 0, cb = 0, a = 0, b = 0;
 7         for(int i : nums)
 8         {
 9             if(ca == i) // 如果i和候选人a是同一个，其票数加一
10                 a++;
11             else if(cb == i) // 同理
12                 b++;
13             else if(!a) // 如果a的票数为0，说明ca是空出来的。要把ca更新为i
14             {
15                 ca = i;
16                 a++;
17             }
18             else if(!b) // 同理
19             {
20                 cb = i;
21                 b++;
22             }
23             else // 出现了三足鼎立的情况，我们把三人的票数都减一。i就代表第三个人，它的默认票数是1
24             {
25                 a--;
26                 b--;
27             }
28         }
29         
30         // 判断候选人是否是符合要求的结果
31         a = 0;
32         b = 0;
33         for(int i : nums)
34         {
35             if(i == ca)
36                 a++;
37             else if(i == cb)
38                 b++;
39         }
40         // 与题目要求匹配
41         if(a > nums.size()/3)
42             ans.push_back(ca);
43         if(b > nums.size()/3)
44             ans.push_back(cb);
45         
46         return ans;
47     }
48 };