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 {
7
8public:
9 //出现次数大于int(n/3)的元素，最少有0个，最多有两个
10 vector<int> majorityElement(vector<int>& nums) {
11 vector<int>res;
12 int n = nums.size();
13 if (n==0) return res;
14 int cnt1,cnt2,v1,v2;
15 cnt1 = cnt2 = 0;
16 v1 = v2 = -1;
17 for ( int i = 0 ; i < n ; i++)
18 {
19 int x = nums[i];
20// printf("i:%d nums[i]:%d v1:%d cnt1:%d v2:%d cnt2:%d\n",i,nums[i],v1,cnt1,v2,cnt2);
21 if (cnt1==0&&v2!=x) //兄弟的女人不要抢(误
22 {
23 cnt1++;
24 v1 = x;
25 continue;
26 }else if ( cnt2==0&&v1!=x) //朋友妻不可欺（？？？
27 {
28 cnt2++;
29 v2 = x;
30 continue;
31 }
32 if (x==v1) cnt1++;
33 else if (x==v2) cnt2++;
34 else
35 {
36 cnt1--;
37 cnt2--;
38 }
39 }
40 int n3 = n/3;
41 int check1=0,check2=0; //未必出现此处大于int(n/3),再检查一次。
42 for ( int i = 0 ; i < n ; i++)
43 {
44 if (nums[i]==v1) check1++;
45 else
46 if (nums[i]==v2) check2++;
47 }
48// cout<<"v1:"<<v1<<" v2:"<<v2<<"c1:"<<check1<<" c2:"<<check2<<endl;
49 if (v1==v2)
50 {
51 if (check1>n3) res.push_back(v1);
52 return res;
53 }
54// cout<<"check1:"<<check1<<" n3:"<<n3<<endl;
55 if (check1>n3)
56 res.push_back(v1);
57 if (check2>n3)
58 res.push_back(v2);
59 return res;
60
61
62 }
63
64};