Majority Number III · 數據結構與算法/leetcode/lintcode題解

# 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<Integer> nums, int k) { HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); 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<Integer, Integer> hash) { Set<Integer> keySet = hash.keySet(); for (int key : keySet) { hash.put(key, hash.get(key) - 1); } /* solution 1 */ Iterator<Map.Entry<Integer, Integer>> it = hash.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Integer> entry = it.next(); if(entry.getValue() == 0) { it.remove(); } } /* solution 2 */ // List<Integer> 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/)