[lintcode]Majority Number III

http://lintcode.com/en/problem/majority-number-iii/

此题是黑帮火并的思想，就是如果有k个不同的元素，那么把他们全去掉，不影响剩下的元素中的“众数”。如果“众数”在k个里面，不影响，不在，也不影响。原题确认只有一个“众数”，那么就不用再扫一遍了。

当然也可以用拉斯维加斯算法，就是猜，猜完了O(n)验证。期待时间是O(k*n)。

代码其实有个问题，不一定是剩下k个里最大的，而是剩下的k个都有可能。

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int majorityNumber(vector<int> nums, int k) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            auto it = hash.find(nums[i]);
            if (it == hash.end()) {
                hash[nums[i]] = 1;
                if (hash.size() == k) {
                    for (auto hit = hash.begin(); hit != hash.end();) {
                        if (--(hit->second) == 0) {
                            hit = hash.erase(hit);
                        }
                        else {
                            hit++;
                        }
                    }
                }
            }
            else {
                it->second++;
            }
        }
        int ret = 0;
        int max_count = 0;
        for (auto hit = hash.begin(); hit != hash.end(); hit++) {
            if (hit->second > max_count) {
                max_count = hit->second;
                ret = hit->first;
            }
        }
        return ret;
    }
};

要注意的是，有的编译器支持在iterate的过程中erase，有的则需要显式的it=hash.erase(it)的操作（例如VS）。