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.

分析：

题目的思路很明确，和majority number II一样，但是实现起来并没有那么简单。注意技巧：当counter满k个以后，先把0的全删除。如果没有0的，再统一 -= 1。

解法：

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
        if (nums.size() == 0) {
            return -1;
        }
        // begin
        unordered_map<int, int> Hash;
        for (int i = 0; i < nums.size(); i++) {
            if (Hash.find(nums[i]) == Hash.end() ) {
                Hash[nums[i] ] = 1;
            } else {
                Hash[nums[i] ] += 1;
            }
            // remove 0s, if exist
            if (Hash.size() == k) {
                vector<int> removeList;
                for (auto it = Hash.begin(); it != Hash.end(); it++) {
                    if (it->second == 0) {
                        removeList.push_back(it->first);
                    }
                }
                for (int i = 0; i < removeList.size(); i++) {
                    Hash.erase(removeList[i]);
                }
            }
            // back-off is no 0 exists
            if (Hash.size() == k) {
                for (auto it = Hash.begin(); it != Hash.end(); it++) {
                    it->second -= 1;
                }
            }
        }
        // counter return to zero
        for (auto it = Hash.begin(); it != Hash.end(); it++) {
            it->second = 0;
        }
        // loop again to find max
        for (int i = 0; i < nums.size(); i++) {
            if (Hash.find(nums[i]) != Hash.end() ) {
                Hash[nums[i] ] += 1;
            }
        }
        // take result
        int maxCount = INT_MIN;
        int maxKey = 0;
        for (auto it = Hash.begin(); it != Hash.end(); it++) {
            if (it->second > maxCount) {
                maxCount = it->second;
                maxKey = it->first;
            }
        }
        return maxKey;
    }
};