Simple Java Solution. O(nlogk) & O(n) Beat 90%


  • 0
    F

    Similar to top k frequent elements.
    I use map to store each word and its frequency. And use a max to get the max frequency. Then create a bucket to put same frequency words together. Then get the top k from bucket. The time complexity is O(k * nlogk) which is O(nlogk). Since in the last loop, we will only traverse at most k times, and each time I will sort the words inside current bucket(Similar to use priorityQueue ).

    class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            HashMap<String, Integer> map = new HashMap<>();
            int max = 0;
            for (String w: words) {
                map.put(w, map.getOrDefault(w, 0) + 1);
                max = Math.max(max, map.get(w));
            }
            List<String>[] bucket = new ArrayList[max + 1];
            for (Map.Entry<String, Integer> entry: map.entrySet()) {
                int fre = entry.getValue();
                if (bucket[fre] == null) {
                    bucket[fre] = new ArrayList<>();
                }
                bucket[fre].add(entry.getKey());
            }
            List<String> res = new ArrayList<>();
            for (int i = max; i >= 0 && res.size() < k; i--) {
                if (bucket[i] != null) {
                    Collections.sort(bucket[i]);
                    res.addAll(bucket[i]);
                }
            }
            return res.subList(0, k);
        }
    }
    

Log in to reply
 

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