leetcode 229. Majority Element II （O(1)空间找出现次数大于n/3的元素）
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
题意：给你n个数，要求找出出现此处大于n/3的。。。
思路：之前做过一个找出n个数出现此处大于n/2的题目，思想是“非吾族类，其心必异”。。
这道题类似。。。容易知道题目要求的数最多有2个，最少有0个。。。
由于最多两个“族类”，在更新的时候，要判断是不是友军的人...毕竟朋友妻不可欺嘛（什么鬼
最后记得扫一遍，check一下，检查出现此处是否满足题意。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 20时05分53秒
4File Name :229.cpp
5************************************************ */
6class Solution {
1public:
2 //出现次数大于int(n/3)的元素，最少有0个，最多有两个
3 vector<int> majorityElement(vector<int>& nums) {
4 vector<int>res;
5 int n = nums.size();
6 if (n==0) return res;
7 int cnt1,cnt2,v1,v2;
8 cnt1 = cnt2 = 0;
9 v1 = v2 = -1;
10 for ( int i = 0 ; i < n ; i++)
11 {
12 int x = nums[i];
13// printf("i:%d nums[i]:%d v1:%d cnt1:%d v2:%d cnt2:%d\n",i,nums[i],v1,cnt1,v2,cnt2);
14 if (cnt1==0&&v2!=x) //兄弟的女人不要抢(误
15 {
16 cnt1++;
17 v1 = x;
18 continue;
19 }else if ( cnt2==0&&v1!=x) //朋友妻不可欺（？？？
20 {
21 cnt2++;
22 v2 = x;
23 continue;
24 }
25 if (x==v1) cnt1++;
26 else if (x==v2) cnt2++;
27 else
28 {
29 cnt1--;
30 cnt2--;
31 }
32 }
33 int n3 = n/3;
34 int check1=0,check2=0; //未必出现此处大于int(n/3),再检查一次。
35 for ( int i = 0 ; i < n ; i++)
36 {
37 if (nums[i]==v1) check1++;
38 else
39 if (nums[i]==v2) check2++;
40 }
41// cout<<"v1:"<<v1<<" v2:"<<v2<<"c1:"<<check1<<" c2:"<<check2<<endl;
42 if (v1==v2)
43 {
44 if (check1>n3) res.push_back(v1);
45 return res;
46 }
47// cout<<"check1:"<<check1<<" n3:"<<n3<<endl;
48 if (check1>n3)
49 res.push_back(v1);
50 if (check2>n3)
51 res.push_back(v2);
52 return res;
}
};