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.

Note

There is only one majority number in the array.

Example

For [3,1,2,3,2,3,3,4,4,4] and k = 3, return 3

Challenge

O(n) time and O(k) extra space'

 
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @param k: As described
     * @return: The majority number
     */
    int majorityNumber(vector<int> nums, int k) {
        unordered_map<int, int> map;
        int n = nums.size();
        
        for(int i = 0; i<n ;i++) 
        {
           if (map.size() < k) {
                map[nums[i]]++;
           }
           else {
               if (map.find(nums[i]) != map.end())
                  map[nums[i]]++;
                else  {
                    vector<int> keys;
                    for(auto iter = map.begin(); iter != map.end();)
                    {
                        if (iter->second == 1)
                           keys.push_back(iter->first);
                          
                        iter->second--;
                        iter++;
                    }
                    
                    for(int kk :keys)
                       map.erase(kk);
                    map[nums[i]] = 1;
                }
           }   
        }
        
        int mx = 0;
        int ret = 0;
        for(auto &iter : map) {
            if (iter.second > mx) {
                ret = iter.first;
                mx = iter.second;
            }
        }
        
        return ret;
    }
};