优先队列leetcode题目解析

2019-04-15 20-37-09 的屏幕截图.png

package structures;


import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

/**
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * <p>
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * <p>
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 */

class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,1,1,2,2,3};
        List<Integer> topKFrequent = solution.topKFrequent(nums, 2);
        System.out.println(topKFrequent);
    }
    /**
     * 解题思路:
     * 1 将数组不同元素及其频次放入字典中
     * 2 以频次作比较将元素和频次封装到类中 放入优先队列中
     * 优先队列中先放入k个元素 最小值优先出队 k个元素之后必须比队首元素大 方可入队
     */
    private class Freq implements Comparable<Freq> {
        public int e, freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq o) {
            return this.freq < o.freq ? 1 : -1;
        }
    }

    //nums = [1,1,1,2,2,3], k = 2
    public List<Integer> topKFrequent(int[] nums, int k) {
        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<Freq> pq = new PriorityQueue<>();
        for (Integer key : map.keySet()) {
            if (pq.getSize() < k) {
                pq.enqueue(new Freq(key, map.get(key)));
            } else {
                if (pq.getFront().freq < map.get(key)) {
                    pq.dequeue();
                    pq.enqueue(new Freq(key, map.get(key)));
                }
            }
        }

        LinkedList<Integer> list = new LinkedList<>();
        while (!pq.isEmpty()) {
            list.add(pq.dequeue().e);
        }
        return list;
    }
}