229. Majority Element II

https://leetcode.com/problems/majority-element-ii/

　　本题大意：给定一个大小为n的正整数数组，求出出现了超过⌊ n/3 ⌋次的元素。要求时间复杂度为o(n)，空间复杂度为o(1)。

　　解题思路：首先要清楚，满足条件的这种元素最多有几个？答案应该是2个。所以我们只需要用两个变量（m1/m2）来存储这两个潜在的元素，用两个变量(c1/c2)来存储他们出现的次数。这就解决了空间复杂度的问题。

　　其次，我们参考Majority Element的思路，只不过这里要更新的是两个值。什么时候更新c1和c2？遇到m1，c1就加1，否则减1；遇到m2，c2就加1，否则就减1。什么时候更新m1和m2？当c1和c2减到0的时候就改变m1和m2的值，同时将c1和c2的值置为1。

　　这里有一个问题，是不是说最终剩下的那两个m1和m2一定是要求得的答案呢？答案是否定的。最坏的情况，即所有元素都不相同时，最终也会得到这样的m1和m2，但是显然m1和m2并不是我们想要的结果。所以距离成功还需要一步：统计这两个值出现的次数。

　　最后，统计m1和m2出现的次数，如果满足大于⌊ n/3 ⌋，那么就是我们期待的结果。

代码如下：

 1 class Solution {
 2 public:
 3     vector<int> majorityElement(vector<int>& nums) {
 4         vector<int> v;
 5         int n = nums.size();
 6         if(n == 0) return v;
 7         if(n == 1) {v.push_back(nums[0]);return v;}
 8         int m1 = nums[0];
 9         int m2 = 0;
10         int c1 = 0;
11         int c2 = 0;
12         for(int i = 0; i < n; i++)
13         {
14             if(nums[i] == m1) ++c1;
15             else if(nums[i] == m2) ++c2;
16             else if(c1 == 0){++c1; m1 = nums[i];}
17             else if(c2 == 0){++c2; m2 = nums[i];}
18             else{--c1; --c2;}
19         }
20         c1 = 0;
21         c2 = 0;
22         for(int i = 0; i < n; i++)
23         {
24             if(nums[i] == m1)
25                 ++c1;
26             if(nums[i] == m2)
27                 ++c2;
28         }
29         if(c1 > n/3)
30             v.push_back(m1);
31         if(m2 != m1 && c2 > n/3)
32             v.push_back(m2);
33         return v;
34 
35     }
36 };