算法---TOPK问题

leetcode topk问题：

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

自己刚开始直接进行操作使用的是大根堆：复杂度有点高

class Solution {
    public List topKFrequent(String[] words, int k) {
        //直接Map添加 A掉啊。。。
               Map map = new linkedHashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }
        PriorityQueue> priorityQueue = new PriorityQueue<>(new Comparator>() {
            @Override
            public int compare(Map.Entry o1, Map.Entry o2) {
                //return o1.getValue() - o2.getValue();
                if (o2.getValue() - o1.getValue() == 0) {
                    if (o2.getKey().length() - o1.getKey().length() > 0) {
                        for (int i = 0; i < o1.getKey().length(); i++) {
                            if (o2.getKey().charAt(i) < o1.getKey().charAt(i)) {
                                return 1;
                            } else if (o2.getKey().charAt(i) > o1.getKey().charAt(i)) {
                                return -1;
                            }
                            if (i == o1.getKey().length() - 1) {
                                return -1;
                            }
                        }
                    } else {
                        for (int i = 0; i < o2.getKey().length(); i++) {
                            if (o2.getKey().charAt(i) < o1.getKey().charAt(i)) {
                                return 1;
                            } else if (o2.getKey().charAt(i) > o1.getKey().charAt(i)) {
                                return -1;
                            }
                            if (i == o2.getKey().length() - 1) {
                                return 1;
                            }
                        }
                    }
                }
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        for (Map.Entry entry : map.entrySet()) {
            priorityQueue.add(entry);
        }
        List result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(priorityQueue.poll().getKey());
        }
        //进行排序取取前K个数据
        return result;
    }
}

构建小根堆进行求解：

题解参考：topk