LeetCode 求众数 II

 1 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
 2 #define PB push_back
 3 #define ft first
 4 #define sd second
 5 
 6 class Solution {
 7 public:
 8     vector<int> majorityElement(vector<int>& nums, int k = 3) {
 9         vector<int> ans;
10         unordered_map< int, int > cnt;
11         int N = nums.size();
12         
13         for(int i = 0; i < N; ++i) {
14             ++cnt[nums[i]];
15             if(cnt.size() >= k) {
16                 vector< __typeof(cnt.begin()) > toDel;
17                 
18                 foreach(x, cnt) {
19                     if(--x->sd == 0) toDel.PB(x);
20                 }
21                 
22                 foreach(x, toDel) cnt.erase(*x);
23             }
24         }
25         
26         foreach(x, cnt) x->sd = 0;
27         
28         for(int i = 0; i < N; ++i) {
29             if(cnt.find(nums[i]) != cnt.end()) ++cnt[nums[i]];
30         }
31         
32         foreach(x, cnt) {
33             if(x->sd * k > N) ans.PB(x->ft);
34         }
35         
36         return ans;
37     }
38 };