Top K largest Numbers

。題目假設

從數組裡找出前 k 大的數

。重要問題

PriorityQueue 的 order是升序還是降序

。直覺

可以用 heap 來做，因為 heap 的特性是會維持第一個元素是 min/max

。解決方法可行性

掃過數組，每次將元素丟進 heap 裡，完成遍歷後，取出前 k 個即可

。解決方案

要開一個大小為 k 的結果數組，

開一個 PriotiyQueue

遍歷 nums ：

將每個元素丟進 PriorityQueue，讓他自動調整順序

取出前 k 個

。資料結構

PriorityQueue

。複雜度

PriorityQueue 插入是 O(log n) ，數組有 n 個元素 => O(nlog n)

。遇到的困難點、想錯的地方

public int[] topk(int[] nums, int k) {
    int[] res = new int[k];
    if (nums == null || nums.length == 0 || nums.length < k) {
        return new int[]{};
    }

    PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
    for (int i=0; i<nums.length; i++) {
        pQ.offer(nums[i]);
    }

    for (int i=0; i<k; i++)
        res[i] = pQ.poll();
    return res;
}

另一個解法是用 quick-select，也就是 quick-sort 的 partition

Top K largest Numbers II

。題目假設

實作一個資料結構包含 add(), topk() 的功能

。重要問題

問清楚！！！！！！！

。直覺

用 PriorityQueue 解決

。解決方法可行性

透過 PriorityQueue 去讓加進來的數自動排序

。解決方案

。資料結構

PriorityQueue

。複雜度

add() : O(log k)

topK() : O(k)

。遇到的困難點、想錯的地方

add() 要問清楚，是可以無限增長的 PriorityQueue，還是只能有 k 個元素的 PriorityQueue?

如果是只能有 k個的PriorityQueue，那就要用 min heap，因為每次加入時要把最小的刪掉

public class Solution {
    private int maxSize;
    private Queue<Integer> minheap;
    public Solution(int k) {
        minheap = new PriorityQueue<>();
        maxSize = k;
    }

    public void add(int num) {
        if (minheap.size() < maxSize) {
            minheap.offer(num);
            return;
        }

        if (num > minheap.peek()) {
            minheap.poll();
            minheap.offer(num);
        }
    }

    public List<Integer> topk() {
        Iterator it = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (it.hasNext()) {
            result.add((Integer) it.next());
        }
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
};