Majority Number III
最后更新于：2022-04-02 01:10:01
# Majority Number III
### Source
- lintcode: [(48) Majority Number III](http://www.lintcode.com/en/problem/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.
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
~~~
### 题解
[Majority Number II](http://algorithm.yuanbin.me/zh-cn/math_and_bit_manipulation/majority_number_ii.html) 的升级版，有了前两道题的铺垫，此题的思路已十分明了，对 K-1个数进行相互抵消，这里不太可能使用 key1, key2...等变量，用数组使用上不太方便，且增删效率不高，故使用哈希表较为合适，当哈希表的键值数等于 K 时即进行清理，当然更准备地来讲应该是等于 K-1时清理。故此题的逻辑即为：1. 更新哈希表，若遇哈希表 size == K 时则执行删除操作，最后遍历哈希表取真实计数器值，返回最大的 key.
### Java
~~~
public class Solution {
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
public int majorityNumber(ArrayList nums, int k) {
HashMap hash = new HashMap();
if (nums == null || nums.isEmpty()) return -1;
// update HashMap
for (int num : nums) {
if (!hash.containsKey(num)) {
hash.put(num, 1);
if (hash.size() >= k) {
removeZeroCount(hash);
}
} else {
hash.put(num, hash.get(num) + 1);
}
}
// reset
for (int key : hash.keySet()) {
hash.put(key, 0);
}
for (int key : nums) {
if (hash.containsKey(key)) {
hash.put(key, hash.get(key) + 1);
}
}
// find max
int maxKey = -1, maxCount = 0;
for (int key : hash.keySet()) {
if (hash.get(key) > maxCount) {
maxKey = key;
maxCount = hash.get(key);
}
}
return maxKey;
}
private void removeZeroCount(HashMap hash) {
Set keySet = hash.keySet();
for (int key : keySet) {
hash.put(key, hash.get(key) - 1);
}
/* solution 1 */
Iterator> it = hash.entrySet().iterator();
while (it.hasNext()) {
Map.Entry entry = it.next();
if(entry.getValue() == 0) {
it.remove();
}
}
/* solution 2 */
// List removeList = new ArrayList<>();
// for (int key : keySet) {
// hash.put(key, hash.get(key) - 1);
// if (hash.get(key) == 0) {
// removeList.add(key);
// }
// }
// for (Integer key : removeList) {
// hash.remove(key);
// }
/* solution3 lambda expression for Java8 */
}
}
~~~
### 源码分析
此题的思路不算很难，但是实现起来还是有点难度的，**Java 中删除哈希表时需要考虑线程安全。**
### 复杂度分析
时间复杂度 O(n)O(n)O(n), 使用了哈希表，空间复杂度 O(k)O(k)O(k).
### Reference
- [Majority Number III 参考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/majority-number-iii/)
';