solution in O(nlog(n)) with HashMap and sort in java(easy to understand)


  • 0
    F

    """

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i], 1);
            }else{
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        List<Pair> pairs = new ArrayList<>();
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            Pair p = new Pair(entry.getKey(), entry.getValue());
            pairs.add(p);
        }
        Collections.sort(pairs);
        List<Integer> result = new ArrayList<>();
        int index = pairs.size() -1;
        while(k > 0){
            result.add(pairs.get(index).number);
            index--;
            k--;
        }
        return result;
    }
    
    public static class Pair implements Comparable {
        int number;
        int freq;
        Pair(int number, int freq){
            this.number = number;
            this.freq = freq;
        }
    
        @Override
        public int compareTo(Object o) {
            return Double.compare(this.freq, ((Pair)o).freq);
        }
    }
    

    """


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.