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.

Hint:

1. How many majority elements could it possibly have?

跟出现超过一半的数差不多，出现超过1/3的数最多有2个，扫描一遍数组，分别计数数组中的元素，当出现3个不同的元素时，把这3个元素都抛弃掉，如果有符合要求的数，那么它一定在最后剩下的数中，再分别判断一下剩下的数就能得到答案。

1 class Solution { 2 public: 3     vector
     
       majorityElement(vector
      
       & nums) { 4         int k = 3; 5         vector
       
         val(k), cnt(k, 0); 6         for (int i = 0; i < nums.size(); ++i) { 7             bool flag = true; 8             for (int j = 0; j < k; ++j)  { 9                 if (val[j] == nums[i] && cnt[j] > 0) {10                     val[j] = nums[i];11                     ++cnt[j];12                     flag = false;13                     break;14                 }15             }16             if (flag) {17                 for (int j = 0; j < k; ++j) {18                     if (cnt[j] == 0) {19                         val[j] = nums[i];20                         ++cnt[j];21                         break;22                     }23                 }24             }25             if (cnt[k - 1] == 1) {26                 for (int kk = 0; kk < k; ++kk) {27                     --cnt[kk];28                 }29             }30         }31         vector
        
          res;32         for (int i = 0; i < k; ++i) if (cnt[i] > 0) {33                 int c = 0;34                 for (auto n : nums) if (val[i] == n) ++c;35                 if (c > nums.size() / k) res.push_back(val[i]);36         }37         return res;38     }39 };