Majority Element III

来源：Lintcode

原帖：http://www.lintcode.com/en/problem/majority-number-iii/

题目：
Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array. Find it. There is only one majority number in the array.
Example
For [3,1,2,3,2,1,3,1,2,3,3,4,4,4] and k = 3, return 3.

代码：

 class Solution {  
 public:  
   int majorityNumber(vector<int> nums, int k) {  
     int n = nums.size();  
     unordered_map<int, int> map; // <key, count>  
     for (int i = 0; i < n; ++i) {  
       if (map.count(nums[i])) {  
         map[nums[i]]++;  
       } else if (map.size() < k) {  
         map[nums[i]] = 1;  
       } else {  
         unordered_set<int> set;  
         for (auto it = map.begin(); it != map.end(); it++) {  
           it->second--;  
           if (it->second == 0) {  
             set.insert(it->first);  
           }  
         }  
         for (auto i : set) {  
           map.erase(i);  
         }  
       }  
     }  
     
     // find all remaining candidates  
     unordered_map<int, int> tmap;  
     for (auto it = map.begin(); it != map.end(); it++) {  
       tmap[it->first] = 0;  
     }  
     
     int count = 0, result = 0;  
     for (int i = 0; i < n; ++i) {  
       if (tmap.find(nums[i]) != tmap.end()) {  
         tmap[nums[i]]++;  
         if (tmap[nums[i]] > count) {  
           count = tmap[nums[i]];  
           result = nums[i];  
         }  
       }  
     }  
     return result;  
   }  
 };