Java solution with HashMap and bucket sort


  • 0
    S

    Here is my solution with HashMap and Bucket sorting. Runtime is 21ms.

    public List<String> topKFrequent(String[] words, int k) {
            // bucket sort
            if(words == null || words.length < 1) return new ArrayList<String>();
            HashMap<String, Integer> maps = new HashMap<String, Integer>();
            for(String word: words){
                if(!maps.containsKey(word)){
                    maps.put(word, 1);
                }else{
                    maps.put(word, maps.get(word)+1);
                }
            }
            List<String>[] buckets = new List[words.length+1];
            for(String key: maps.keySet()){
                int val = maps.get(key);
                if(buckets[val] == null){
                    buckets[val] = new ArrayList<String>();
                }
                buckets[val].add(key);
                
            }
            List<String> result = new ArrayList<String>();
            for(int i=words.length; i>=0; i--){
                if(buckets[i] != null){
                    Collections.sort(buckets[i]);
                    for(String s: buckets[i]){
                        result.add(s);
                        if(result.size() == k) return result;
                    }
                }
            }
            return result;
        }
    
    

  • 0
    Y

    @Sallyqifeng
    Hi, I think the time complexity of your algorithm is O(nlogn) in the worst case.
    Because you use Collections.sort() in the last part.
    For instance, the worst case: ["is", "a", "sunny", "day"], k = 2.


  • 0
    S

    @yro yeah, but I think this kind of sorting is unavoidable... Is there any optimization for this?


  • 0
    Y

    @Sallyqifeng
    Currently, I cannot figure out a better way without sorting if PRIORITY QUEUE is used. But I have come up with another solution which replaces priority queue with a trie. You can refer to this post. Comments are always welcomed.


Log in to reply
 

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