692. Top K Frequent Words有点不太懂

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
         List<String> result = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<words.length; i++)
        {
            if(map.containsKey(words[i]))
                map.put(words[i], map.get(words[i])+1);
            else
                map.put(words[i], 1);
        }

        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>
        (
            (a,b) -> a.getValue().equals(b.getValue()) ?
            b.getKey().compareTo(a.getKey()) :                                                                       
            Integer.compare(a.getValue(),b.getValue())
        );

        for(Map.Entry<String, Integer> entry: map.entrySet())
        {
            pq.offer(entry);
            if(pq.size()>k)
                pq.poll();
        }

        while(!pq.isEmpty())
            result.add(0, pq.poll().getKey());

        return result;
    }
}
在 PriorityQueue  comparator 里面为什么吧 b.getKey().compareTo(a.getKey()) 写成 a.getKey().compareTo(b.getKey()) 就不行了，comparator 到底是怎么排序的？

你这个问题我不是特别懂，我感觉你懂comparator， 但是似乎又是在问到底comparator怎么排序。。

先说这个pq。 按题目来说， 是要频率高的朝前拍， 如果频率一样高， 那就按字典序排。但是这个人写的是一个min pq， 所以是先按频率低的出， 如果频率一样， 就出字典序大的单词。

这也就是为什么他这里写成  (a,b) -> a.getValue().equals(b.getValue()) ? b.getKey().compareTo(a.getKey()) : Integer.compare(a.getValue(),b.getValue()) | 解读： [a, b] 相比， 频率一样吗？ 字典序大的先 ： 频率低的先

所以每次min pq 里面的空间大于K时， 就poll。

再来回答你的问题， Comparator 到底怎么排序的？

其实说难不难， 这都要怪1.8里面出了一个lambda expression， 对于1.8以前的人， 这段代码都得乖乖写成一个Comparator （anonymous）class

正经写的话， 应该是在外面加一个

```
class CompareByFreqThenLexi implements Comparator<Map.Entry<String, Integer>>
{
        public int compare(Map<String, Integer> o1, Map<String, Integer> o2)
        {
                int v1 = o1.getValue(), v2 = o2.getValue();
                if(v1 == v2)
                {
                        String s1 = o1.getKey(), s2 = o2.getKey();
                        return s2.compareTo(s1);
                }
                return v1 - v2;
        }
}
```

或者是像他这段， 只不过不是lambda expression， 而是加一个anonymous class
```
    PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(new Comparator<Map<String, Integer>>()
    {
        public int compare(Map<String, Integer> o1, Map<String, Integer> o2)
        {
                int v1 = o1.getValue(), v2 = o2.getValue();
                if(v1 == v2)
                {
                        String s1 = o1.getKey(), s2 = o2.getKey();
                        return s2.compareTo(s1);
                }
                return v1 - v2;
        }
    });
```

现在是1.8时代了， 当然可以用lambda expression, 也就是你的例子中的这个。

不过我个人建议是， 如果你不太熟悉。。还是写comparator class。 或者这个写出来不是一句话， 就还是别这样折腾自己了。

送你一段这个题我写的[不太长的]方法。

```
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for(String word : words) map.put(word, map.getOrDefault(word, 0) + 1);
        List<String> list = new ArrayList<>(map.keySet());
        Collections.sort(list, (a, b) -> (map.get(b) == map.get(a) ? a.compareTo(b) : map.get(b) - map.get(a)));
        return list.subList(0, k);
    }
```

其实意思都一样了o(￣ヘ￣o＃)


补充内容 (2018-7-11 11:30):
如果你comparator class不太懂的话， 上网找点材料或者视频学习一下就好了， 挺容易理解的。

comparator 默认是最小堆