Majority Number III

Question

  1. Given an array of integers and a number k,
  2. the majority number is the number that occurs more than 1/k of the size of the array.
  4. Find it.
  6. Example
  7. Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.
  9. Note
  10. There is only one majority number in the array.
  12. Challenge
  13. O(n) time and O(k) extra space

题解

Majority Number II 的升级版，有了前两道题的铺垫，此题的思路已十分明了，对 K-1个数进行相互抵消，这里不太可能使用 key1, key2…等变量，用数组使用上不太方便，且增删效率不高，故使用哈希表较为合适，当哈希表的键值数等于 K 时即进行清理，当然更准备地来讲应该是等于 K-1时清理。故此题的逻辑即为：1. 更新哈希表，若遇哈希表 size == K 时则执行删除操作，最后遍历哈希表取真实计数器值，返回最大的 key.

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param nums: A list of integers
  5.      * @param k: As described
  6.      * @return: The majority number
  7.      */
  8.     int majorityNumber(vector<int> nums, int k) {
  9.         unordered_map<int, int> map;
  11.         for (auto n : nums) {
  12.            if (map.size() < k) map[n]++;
  13.            else {
  14.                 if (map.count(n)) map[n]++;
  15.                 else {
  16.                     map[n] = 1;
  17.                     vector<int> keys;
  18.                     for (auto &it : map) {
  19.                         it.second--;
  20.                         if (!it.second) keys.push_back(it.first);
  21.                     }
  22.                     for (int i : keys) map.erase(i);
  23.                 }
  24.             }   
  25.         }
  27.         int mx = 0;
  28.         int ret = 0;
  29.         for (auto &it : map) {
  30.             if (it.second > mx) {
  31.                 ret = it.first;
  32.                 mx = it.second;
  33.             }
  34.         }
  35.         return ret;
  36.     }
  37. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @param k: As described
  5.      * @return: The majority number
  6.      */
  7.     public int majorityNumber(ArrayList<Integer> nums, int k) {
  8.         HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
  9.         if (nums == null || nums.isEmpty()) return -1;
  11.         // update HashMap
  12.         for (int num : nums) {
  13.             if (!hash.containsKey(num)) {
  14.                 hash.put(num, 1);
  15.                 if (hash.size() >= k) {
  16.                     removeZeroCount(hash);
  17.                 }
  18.             } else {
  19.                 hash.put(num, hash.get(num) + 1);
  20.             }
  21.         }
  23.         // reset
  24.         for (int key : hash.keySet()) {
  25.             hash.put(key, 0);
  26.         }
  27.         for (int key : nums) {
  28.             if (hash.containsKey(key)) {
  29.                 hash.put(key, hash.get(key) + 1);
  30.             }
  31.         }
  33.         // find max
  34.         int maxKey = -1, maxCount = 0;
  35.         for (int key : hash.keySet()) {
  36.             if (hash.get(key) > maxCount) {
  37.                 maxKey = key;
  38.                 maxCount = hash.get(key);
  39.             }
  40.         }
  42.         return maxKey;
  43.     }
  45.     private void removeZeroCount(HashMap<Integer, Integer> hash) {
  46.         Set<Integer> keySet = hash.keySet();
  47.         for (int key : keySet) {
  48.             hash.put(key, hash.get(key) - 1);
  49.         }
  51.         /* solution 1 */
  52.         Iterator<Map.Entry<Integer, Integer>> it = hash.entrySet().iterator();
  53.         while (it.hasNext()) {
  54.             Map.Entry<Integer, Integer> entry = it.next();
  55.             if(entry.getValue() == 0) {
  56.                 it.remove();
  57.             }
  58.         }
  60.         /* solution 2 */
  61.         // List<Integer> removeList = new ArrayList<>();
  62.         // for (int key : keySet) {
  63.         //     hash.put(key, hash.get(key) - 1);
  64.         //     if (hash.get(key) == 0) {
  65.         //         removeList.add(key);
  66.         //     }
  67.         // }
  68.         // for (Integer key : removeList) {
  69.         //     hash.remove(key);
  70.         // }
  72.         /* solution3 lambda expression for Java8 */
  73.     }
  74. }

源码分析

此题的思路不算很难，但是实现起来还是有点难度的，Java 中删除哈希表时需要考虑线程安全。

复杂度分析

时间复杂度 O(n), 使用了哈希表，空间复杂度 O(k).

Reference