Majority Number III

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

----------------------------- thinking -------------------------------------
http://codeanytime.blogspot.com/2014/12/majority-number-iii.html
http://www.cnblogs.com/lishiblog/p/4189468.html
----------------------------- codes ---------------------------------------
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @param k: As described
     * @return: The majority number
     */
    int majorityNumber(vector<int> nums, int k) {
        // write your code here
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            if (map.find(nums[i]) == map.end()) {
                if (map.size() < k) {
                    map[nums[i]] = 1;
                } else {
                    vector<int> zero_keys;
                    for (auto it = map.begin(); it != map.end(); ++it) {
                        it->second--;
                        if (it->second == 0) {
                            zero_keys.push_back(it->first);
                        }
                    }
                    for (int k = 0; k < zero_keys.size(); k++) {
                        map.erase(zero_keys[k]);
                    }
                }
            } else {
                map[nums[i]] = map[nums[i]] + 1;
            }
        }
        int res = map.begin()->first;
        int val = map.begin()->second;
        for (auto it = map.begin(); it != map.end(); ++it) {
            if (it->second > val) {
                res = it->first;
                val = it->second;
            }
        }
        return res;
    }
};