LintCode 主元素 III题目分析代码

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) {
        // write your code
        
        HashMap<Integer, Integer> counters = new HashMap<>();
        
        for(Integer i:nums) {
            if(!counters.containsKey(i)) {
                counters.put(i, 1);
            } else {
                counters.put(i, counters.get(i)+1);
            }
            
            if(counters.size()>=k)
                removeKey(counters);
        }
        
        // corner case
        if (counters.size() == 0) {
            return Integer.MIN_VALUE;
        }
        
        // recalculate counters
        for(Integer i:counters.keySet()) {
            counters.put(i, 0);
        }
        
        for(Integer i:nums) {
            if(counters.containsKey(i))
                counters.put(i, counters.get(i)+1);
        }
        
        // find the max key
        int maxCounter = 0, maxKey = 0;
        for(Integer key:counters.keySet()) {
            if(counters.get(key) > maxCounter) {
                maxCounter = counters.get(key);
                maxKey = key;
            }
        }
        
        return maxKey;
    }
    
    private void removeKey(HashMap<Integer, Integer> counters) {
        Set<Integer> keySet = counters.keySet();
        ArrayList<Integer> remove = new ArrayList<>();
        for(Integer key:keySet) {
            counters.put(key, counters.get(key)-1);
            if(counters.get(key) == 0) {
                remove.add(key);
            }
        }
        
        for(Integer i:remove) {
            counters.remove(i);
        }
    }
}