Majority Number III(Medium)

From Lintcode

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. Challenge

O(n) time and O(k) extra space

Same as above, As there could be at most (k – 1) elements occuring more than 1 / k of the array, we have (k – 1) slots for majority number candidates. The voting rule is the same as above.

Careful for the ConcurrentModificationException in HashMap, we should remove (write) the keys during the HashMap being iterated (read). Write the hashmap after read.

     public int majorityNumber(ArrayList<Integer> nums, int k) {
        // write your code
        if (nums == null || nums.size() == 0) {
            return -1;
        }
        //map <number, #votes>
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int n : nums) {
            if (!map.containsKey(n)) {
                if (map.size() > k - 1) {
                    //if all slots occupied, vote negative to all elements
                    voteNegative(map);
                } else { 
                    //get an available slot and vote positive
                    map.put(n, 1);
                }
            } else {
                //vote positive
                map.put(n, map.get(n) + 1);
            }
        }
        int maxKey = 0;
        int maxCount = 0;
        for (int key : map.keySet()) {
            if (map.get(key) > maxCount) {
                maxCount = map.get(key);
                maxKey = key;
            }
        }
        return maxKey;
    }

    private void voteNegative(Map<Integer, Integer> map) {
        Set<Integer> keySet = map.keySet();
        List<Integer> removeList = new ArrayList<>();
        for (Integer key : keySet) {
            if (map.get(key) == 1) {
                removeList.add(key);
            } else {
                map.put(key, map.get(key) - 1);
            }
        }
        //remove candidates with 0 votes and free the slot
        for (Integer key : removeList) {
            map.remove(key);
        }
    }