An Easy Understanding Java Solution.


  • 0
    X
    class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            //给定单词数组,返回出现最多频率最多的前k个单词,如果存在频率相同的单词,则按单词顺序排序
            //要求:输入的单词均为小写,k一定在有效范围呢。时间复杂度O(nlogk),n个额外空间
            //思路:使用HashMap<String,Integer>的String作为key,数组下标作为value和List<String>集合数组来存储以频率作为下标
    
            List<String>[] bucket = new List[words.length + 1];
            HashMap<String, Integer> hm = new HashMap<String, Integer>();
    
            for (int i = 0; i < words.length; i++) {
                //因为key是String类型,不能用contains这种对int的判断方法判断
                hm.put(words[i], hm.getOrDefault(words[i], 0) + 1);
            }
    
            //将频数作为下标放入数组
            for (String key : hm.keySet()) {
                int value = hm.get(key);
                //判断是否之前已经存储了单词,没有的话新创建list集合
                if (bucket[value] == null) {
                    bucket[value] = new ArrayList<>();
                }
                bucket[value].add(key);
            }
    
            //将结果输出
            List<String> list = new ArrayList<>();
            for (int i = bucket.length - 1; i >= 0 && list.size() < k; i--) {
                if (bucket[i] != null) {
                    //说明里面有元素
                    String[] strs = bucket[i].toArray(new String[bucket[i].size()]);
                    //将里面的单词排序
                    Arrays.sort(strs);
                    for (String word : strs) {
                        if (list.size() == k) break;
                        list.add(word);
                    }
                }
            }
            return list;
        }
    }
    

Log in to reply
 

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