Description:
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.
Example
Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.
Note
There is only one majority number in the array.
Challenge
O(n) time and O(k) extra space
Solution:
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
auto sz = (int)nums.size();
unordered_map<int, int> cache;
for (int i = 0; i < sz; ++i) {
auto tmp = nums[i];
if (cache.find(tmp) != cache.end())
++cache[tmp];
else if (cache.size() < k)
cache[tmp] = 1;
else {
vector<int> gc;
for (auto& e : cache)
if (--e.second == 0)
gc.push_back(e.first);
for (auto e : gc) cache.erase(e);
}
}
int rc = 0, maxn = 0;
for (auto& e : cache) {
if (e.second > maxn) {
maxn = e.second;
rc = e.first;
}
}
return rc;
}
};
转载于:https://www.cnblogs.com/deofly/p/majority-number-iii.html
相关资源：JAVA上百实例源码以及开源项目
