题目地址 (opens new window)

  • 😣 第一次练习 2020å¹´3月19日 听了老师的讲解使用有线队列。整体思路还是有点的,不过空间和时间度都有点高。
  • 💩 第二次练习

# 优先队列

解题代码

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.TreeMap;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        /**
         * 1. count -> TreeMap(ele, num)
         * 2. new -> PriorityQueue(comparateor)
         * 3. loop keyset e
         *      if pq.size < k
         *          pq.enqueue
         *      else if pq.getFront() < e
         *          pq.remove ; pq.equeue
         * 4. define list -> while pq.isEmpty pq.remove
         */
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            if (map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (Integer num : map.keySet()) {
            if (pq.size() < k)
                pq.add(num);
            else if (map.get(pq.peek()) < map.get(num)) {
                pq.remove();
                pq.add(num);
            }
        }

        ArrayList<Integer> list = new ArrayList<>();
        while (!pq.isEmpty())
            list.add(pq.remove());

        return list;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

# 易错点

  • 在优先队列满时,比较优先队列的最小值时,需要对比是的他们在map中的次数,而不是直接就和最小值进行比较
最后编辑时间: 7/14/2020, 9:21:47 AM