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.

求主元素，这次的是大于sz/3就算是主元素，可以分为两轮查找，第一轮先查找元素数目较多的两个元素（可能不属于主元素），第二次再遍历来查找上面两个元素是否符合条件，代码如下：

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