數(shù)據(jù)結(jié)構(gòu)與算法(4)——優(yōu)先隊(duì)列和堆

前言：題圖無關(guān)，接下來開始簡(jiǎn)單學(xué)習(xí)學(xué)習(xí)優(yōu)先隊(duì)列和堆的相關(guān)數(shù)據(jù)結(jié)構(gòu)的知識(shí)；

前序文章：

什么是優(yōu)先隊(duì)列？

聽這個(gè)名字就能知道，優(yōu)先隊(duì)列也是一種隊(duì)列，只不過不同的是，優(yōu)先隊(duì)列的出隊(duì)順序是按照優(yōu)先級(jí)來的；在有些情況下，可能需要找到元素集合中的最小或者最大元素，可以利用優(yōu)先隊(duì)列ADT來完成操作，優(yōu)先隊(duì)列ADT是一種數(shù)據(jù)結(jié)構(gòu)，它支持插入和刪除最小值操作（返回并刪除最小元素）或刪除最大值操作（返回并刪除最大元素）；

這些操作等價(jià)于隊(duì)列的enQueue和deQueue操作，區(qū)別在于，對(duì)于優(yōu)先隊(duì)列，元素進(jìn)入隊(duì)列的順序可能與其被操作的順序不同，作業(yè)調(diào)度是優(yōu)先隊(duì)列的一個(gè)應(yīng)用實(shí)例，它根據(jù)優(yōu)先級(jí)的高低而不是先到先服務(wù)的方式來進(jìn)行調(diào)度；

如果最小鍵值元素?fù)碛凶罡叩膬?yōu)先級(jí)，那么這種優(yōu)先隊(duì)列叫作升序優(yōu)先隊(duì)列（即總是先刪除最小的元素），類似的，如果最大鍵值元素?fù)碛凶罡叩膬?yōu)先級(jí)，那么這種優(yōu)先隊(duì)列叫作降序優(yōu)先隊(duì)列（即總是先刪除最大的元素）；由于這兩種類型時(shí)對(duì)稱的，所以只需要關(guān)注其中一種，如升序優(yōu)先隊(duì)列；

優(yōu)先隊(duì)列ADT

下面操作組成了優(yōu)先隊(duì)列的一個(gè)ADT；

1.優(yōu)先隊(duì)列的主要操作
優(yōu)先隊(duì)列是元素的容器，每個(gè)元素有一個(gè)相關(guān)的鍵值；

  • insert(key, data)：插入鍵值為key的數(shù)據(jù)到優(yōu)先隊(duì)列中，元素以其key進(jìn)行排序；
  • deleteMin/deleteMax：刪除并返回最小/最大鍵值的元素；
  • getMinimum/getMaximum：返回最小/最大劍指的元素，但不刪除它；

2.優(yōu)先隊(duì)列的輔助操作

  • 第k最小/第k最大：返回優(yōu)先隊(duì)列中鍵值為第k個(gè)最小/最大的元素；
  • 大?。╯ize）：返回優(yōu)先隊(duì)列中的元素個(gè)數(shù)；
  • 堆排序（Heap Sort）：基于鍵值的優(yōu)先級(jí)將優(yōu)先隊(duì)列中的元素進(jìn)行排序；

優(yōu)先隊(duì)列的應(yīng)用

  • 數(shù)據(jù)壓縮：赫夫曼編碼算法；
  • 最短路徑算法：Dijkstra算法；
  • 最小生成樹算法：Prim算法；
  • 事件驅(qū)動(dòng)仿真：顧客排隊(duì)算法；
  • 選擇問題：查找第k個(gè)最小元素；
  • 等等等等....

優(yōu)先隊(duì)列的實(shí)現(xiàn)比較

實(shí)現(xiàn) 插入 刪除 尋找最小值
無序數(shù)組 1 n n
無序鏈表 1 n n
有序數(shù)組 n 1 1
有序鏈表 n 1 1
二叉搜索樹 logn(平均) logn(平均) logn(平均)
平衡二叉搜索樹 logn logn logn
二叉堆 logn logn 1

堆和二叉堆

什么是堆

堆是一顆具有特定性質(zhì)的二叉樹，堆的基本要求就是堆中所有結(jié)點(diǎn)的值必須大于或等于（或小于或等于）其孩子結(jié)點(diǎn)的值，這也稱為堆的性質(zhì)；堆還有另一個(gè)性質(zhì)，就是當(dāng) h > 0 時(shí)，所有葉子結(jié)點(diǎn)都處于第 h 或 h - 1 層（其中 h 為樹的高度，完全二叉樹），也就是說，堆應(yīng)該是一顆完全二叉樹；

在下面的例子中，左邊的樹為堆（每個(gè)元素都大于其孩子結(jié)點(diǎn)的值），而右邊的樹不是堆（因?yàn)?大于其孩子結(jié)點(diǎn)2）

二叉堆

在二叉堆中，每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，在實(shí)際應(yīng)用中，二叉堆已經(jīng)足夠滿足需求，因此接下來主要討論二叉最小堆和二叉最大堆；

堆的表示：在描述堆的操作前，首先來看堆是怎樣表示的，一種可能的方法就是使用數(shù)組，因?yàn)槎言谛问缴鲜且活w完全二叉樹，用數(shù)組來存儲(chǔ)它不會(huì)浪費(fèi)任何空間，例如下圖：

用數(shù)組來表示堆不僅不會(huì)浪費(fèi)空間還具有一定的優(yōu)勢(shì)：

  • 每個(gè)結(jié)點(diǎn)的左孩子為下標(biāo)i的2倍：left child(i) = i * 2；每個(gè)結(jié)點(diǎn)的右孩子為下標(biāo)i的2倍加1：right child(i) = i * 2 + 1
  • 每個(gè)結(jié)點(diǎn)的父親結(jié)點(diǎn)為下標(biāo)的二分之一：parent(i) = i / 2，注意這里是整數(shù)除，2和3除以2都為1，大家可以驗(yàn)證一下；
  • 注意：這里是把下標(biāo)為0的地方空出來了的，主要是為了方便理解，如果0不空出來只需要在計(jì)算的時(shí)候把i值往右偏移一個(gè)位置就行了（也就是加1，大家可以試試，下面的演示也采取這樣的方式）；

二叉堆的相關(guān)操作

堆的基本結(jié)構(gòu)

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    public MaxHeap(int capacity){ data = new Array<>(capacity); }
    public MaxHeap(){ data = new Array<>(); }
    // 返回堆中的元素個(gè)數(shù)
    public int size(){ return data.getSize(); }
    // 返回一個(gè)布爾值, 表示堆中是否為空
    public boolean isEmpty(){ return data.isEmpty(); }
    // 返回完全二叉樹的數(shù)組表示中，一個(gè)索引所表示的元素的父親節(jié)點(diǎn)的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }
    // 返回完全二叉樹的數(shù)組表示中，一個(gè)索引所表示的元素的左孩子節(jié)點(diǎn)的索引
    private int leftChild(int index){ return index * 2 + 1; }
    // 返回完全二叉樹的數(shù)組表示中，一個(gè)索引所表示的元素的右孩子節(jié)點(diǎn)的索引
    private int rightChild(int index){ return index * 2 + 2; }
}

向堆中添加元素和Sift Up

當(dāng)插入一個(gè)元素到堆中時(shí)，它可能不滿足堆的性質(zhì)，在這種情況下，需要調(diào)整堆中元素的位置使之重新變成堆，這個(gè)過程稱為堆化（heapifying）；在最大堆中，要堆化一個(gè)元素，需要找到它的父親結(jié)點(diǎn)，如果不滿足堆的基本性質(zhì)則交換兩個(gè)元素的位置，重復(fù)該過程直到每個(gè)結(jié)點(diǎn)都滿足堆的性質(zhì)為止，下面我們來模擬一下這個(gè)過程：

下面我們?cè)谠摱阎胁迦胍粋€(gè)新的元素26：

我們通過索引（上面的公式）可以很容易地找到新插入元素的父親結(jié)點(diǎn)，然后比較它們的大小，如果新元素更大則交換兩個(gè)元素的位置，這個(gè)操作就相當(dāng)于把該元素上浮了一下：

重復(fù)該操作直到26到了一個(gè)滿足堆條件的位置，此時(shí)就完成了插入的操作：

對(duì)應(yīng)的代碼如下：

// 向堆中添加元素
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int k){

    while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
        data.swap(k, parent(k));
        k = parent(k);
    }
}

取出堆中的最大元素和Sift Down

如果理解了上述的過程，那么取出堆中的最大元素（堆頂元素）將變得容易，不過這里運(yùn)用到一個(gè)小技巧，就是用最后一個(gè)元素替換掉棧頂元素，然后把最后一個(gè)元素刪除掉，這樣一來元素的總個(gè)數(shù)也滿足條件，然后只需要把棧頂元素依次往下調(diào)整就好了，這個(gè)操作就叫做Sift Down（下沉）：

用最后元素替換掉棧頂元素，然后刪除最后一個(gè)元素：

然后比較其孩子結(jié)點(diǎn)的大?。?/p>

如果不滿足堆的條件，那么就跟孩子結(jié)點(diǎn)中較大的一個(gè)交換位置：

重復(fù)該步驟，直到16到達(dá)合適的位置：

完成取出最大元素的操作：

對(duì)應(yīng)的代碼如下：

// 看堆中的最大元素
public E findMax(){
    if(data.getSize() == 0)
        throw new IllegalArgumentException("Can not findMax when heap is empty.");
    return data.get(0);
}

// 取出堆中最大元素
public E extractMax(){

    E ret = findMax();

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);

    return ret;
}

private void siftDown(int k){

    while(leftChild(k) < data.getSize()){
        int j = leftChild(k); // 在此輪循環(huán)中,data[k]和data[j]交換位置
        if( j + 1 < data.getSize() &&
                data.get(j + 1).compareTo(data.get(j)) > 0 )
            j ++;
        // data[j] 是 leftChild 和 rightChild 中的最大值

        if(data.get(k).compareTo(data.get(j)) >= 0 )
            break;

        data.swap(k, j);
        k = j;
    }
}

Replace 和 Heapify

Replace這個(gè)操作其實(shí)就是取出堆中最大的元素之后再新插入一個(gè)元素，常規(guī)的做法是取出最大元素之后，再利用上面的插入新元素的操作對(duì)堆進(jìn)行Sift Up操作，但是這里有一個(gè)小技巧就是直接使用新元素替換掉堆頂元素，之后再進(jìn)行Sift Down操作，這樣就把兩次O(logn）的操作變成了一次O(logn)：

// 取出堆中的最大元素，并且替換成元素e
public E replace(E e){

    E ret = findMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}

Heapify翻譯過來就是堆化的意思，就是將任意數(shù)組整理成堆的形狀，通常的做法是遍歷數(shù)組從0開始添加創(chuàng)建一個(gè)新的堆，但是這里存在一個(gè)小技巧就是把當(dāng)前數(shù)組就看做是一個(gè)完全二叉樹，然后從最后一個(gè)非葉子結(jié)點(diǎn)開始進(jìn)行Sift Down操作就可以了，最后一個(gè)非葉子結(jié)點(diǎn)也很好找，就是最后一個(gè)結(jié)點(diǎn)的父親結(jié)點(diǎn)，大家可以驗(yàn)證一下：

從22這個(gè)節(jié)點(diǎn)開始，依次開始Sift Down操作：

重復(fù)該過程直到堆頂元素：

完成堆化操作：

將n個(gè)元素逐個(gè)插入到一個(gè)空堆中，算法復(fù)雜度是O(nlogn)，而heapify的過程，算法復(fù)雜度為O(n)，這是有一個(gè)質(zhì)的飛躍的，下面是代碼：

public MaxHeap(E[] arr){
    data = new Array<>(arr);
    for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
        siftDown(i);
}

基于堆的優(yōu)先隊(duì)列

首先我們的隊(duì)列仍然需要繼承我們之前將隊(duì)列時(shí)候聲明的哪個(gè)接口Queue，然后實(shí)現(xiàn)這個(gè)接口中的方法就可以了，之類簡(jiǎn)單寫一下：

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue(){ maxHeap = new MaxHeap<>(); }
    @Override
    public int getSize(){ return maxHeap.size(); }
    @Override
    public boolean isEmpty(){ return maxHeap.isEmpty(); }
    @Override
    public E getFront(){ return maxHeap.findMax(); }
    @Override
    public void enqueue(E e){ maxHeap.add(e); }
    @Override
    public E dequeue(){ return maxHeap.extractMax(); }
}

Java中的PriorityQueue

在Java中也實(shí)現(xiàn)了自己的優(yōu)先隊(duì)列java.util.PriorityQueue，與我們自己寫的不同之處在于，Java中內(nèi)置的為最小堆，然后就是一些函數(shù)名不一樣，底層還是維護(hù)了一個(gè)Object類型的數(shù)組，大家可以戳戳看有什么不同，另外如果想要把最小堆變成最大堆可以給PriorityQueue傳入自己的比較器，例如：

// 默認(rèn)為最小堆
PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(5);
pq.add(2);
pq.add(1);
pq.add(10);
pq.add(3);

while (!pq.isEmpty()) {
    System.out.println(pq.poll() + ", ");
}
System.out.println();
System.out.println("————————————————————————");

// 使用Lambda表達(dá)式傳入自己的比較器轉(zhuǎn)換成最大堆
PriorityQueue<Integer> pq2 = new PriorityQueue<>((a, b) -> b - a);
pq2.add(5);
pq2.add(2);
pq2.add(1);
pq2.add(10);
pq2.add(3);

while (!pq2.isEmpty()) {
    System.out.println(pq2.poll() + ", ");
}

LeetCode相關(guān)題目整理

23. 合并K個(gè)排序鏈表

參考答案：（85ms）

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));
    for (int i = 0; i < lists.length; i++) {
        if (lists[i] != null) {
            q.add(lists[i]);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (!q.isEmpty()) {
        tail.next = q.poll();
        tail = tail.next;
        if (tail.next != null) {
            q.add(tail.next);
        }
    }

    return dummy.next;
}

215. 數(shù)組中的第K個(gè)最大元素

我的答案：（75ms）

public int findKthLargest(int[] nums, int k) {

    // 正確性判斷
    if (0 == nums.length || null == nums || k <= 0 || k > nums.length) {
        return -1;
    }

    // 構(gòu)造優(yōu)先隊(duì)列,默認(rèn)為最小堆,傳入自定義的比較器轉(zhuǎn)換成最大堆
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    for (Integer num : nums) {
        pq.add(num);
    }
    for (int i = 0; i < k - 1; i++) {
        pq.remove();
    }
    return pq.peek();
}

參考答案：（5ms）

public int findKthLargest(int[] nums, int k) {
    if (nums.length == 1) {
        return nums[0];
    }

    int max = nums[0];
    int min = nums[0];

    for (int i : nums) {
        max = i > max ? i : max;
        min = i < min ? i : min;
    }

    int[] arrs = new int[max - min + 1];

    for (int i : nums) {
        arrs[max - i]++;
    }

    int pos = 0;
    for (int i = 0; i < arrs.length; i++) {
        pos += arrs[i];
        if (pos >= k) {
            return max - i;
        }
    }

    return nums[0];
}

還看到一個(gè)簡(jiǎn)單粗暴的，也是服了：（4ms）

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

而且我隨機(jī)生成了一個(gè)100萬數(shù)據(jù)的隨機(jī)數(shù)組，來測(cè)試這個(gè)簡(jiǎn)單粗暴的方法的效率，發(fā)現(xiàn)當(dāng)數(shù)據(jù)量上去之后，排序這個(gè)操作變得繁瑣，我自己測(cè)試的時(shí)候，上面三個(gè)方法，第三個(gè)大概比第一個(gè)（我自己寫的方法）多花僅4倍的時(shí)間；

239. 滑動(dòng)窗口最大值（類似劍指Offer面試題59）

參考答案：（88ms）

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || k <= 0) return new int[0];
    int[] res = new int[nums.length - k + 1];
    ArrayDeque<Integer> deque = new ArrayDeque<Integer>();

    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peek() < i - k + 1) // Ensure deque's size doesn't exceed k
            deque.poll();

        // Remove numbers smaller than a[i] from right(a[i-1]) to left, to make the first number in the deque the largest one in the window      
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            deque.pollLast();

        deque.offer(i);// Offer the current index to the deque's tail

        if (i >= k - 1)// Starts recording when i is big enough to make the window has k elements 
            res[index++] = nums[deque.peek()];
    }
    return res;
}

參考答案2：（9ms）

public int[] maxSlidingWindow(int[] nums, int k) {
/*
思想：依次遍歷數(shù)組，有效范圍在長(zhǎng)度k內(nèi)尋找當(dāng)前最大值，在用result數(shù)組來依次存儲(chǔ)當(dāng)前長(zhǎng)度K內(nèi)的最大值；
     若在當(dāng)前輪中出現(xiàn)新增的nums[end]大于curMax,直接替換即可；
     如果當(dāng)前輪curMax不是新增的nums[end]，在新的范圍內(nèi)重置curMax.
*/
    if (nums.length == 0 || k <= 0)
        return new int[0];
    int curMax = Integer.MIN_VALUE;
    for (int i = 0; i < k; i++) {
        if (nums[i] > curMax)
            curMax = nums[i];
    }
    int[] ans = new int[nums.length - k + 1];
    ans[0] = curMax;

    for (int start = 1; start + k - 1 < nums.length; start++) {
        int end = start + k - 1;
        if (nums[end] > curMax)
            curMax = nums[end];
        else if (nums[start - 1] == curMax) {//新增的不大于curMax，新范圍內(nèi)重置
            curMax = Integer.MIN_VALUE;
            for (int i = start; i <= end; i++) {
                if (nums[i] > curMax)
                    curMax = nums[i];
            }
        }
        ans[start] = curMax;
    }
    return ans;
}

264. 丑數(shù) II（劍指Offer面試題49）

參考答案：（7ms）

public int nthUglyNumber(int n) {
    // 正確性判斷
    if (n < 1 || n > 1690) {
        return -1;
    }
    int[] ugly = new int[n];
    ugly[0] = 1;
    int index2 = 0, index3 = 0, index5 = 0;
    int factor2 = 2, factor3 = 3, factor5 = 5;
    for (int i = 1; i < n; i++) {
        int min = Math.min(Math.min(factor2, factor3), factor5);
        ugly[i] = min;
        if (factor2 == min)
            factor2 = 2 * ugly[++index2];
        if (factor3 == min)
            factor3 = 3 * ugly[++index3];
        if (factor5 == min)
            factor5 = 5 * ugly[++index5];
    }
    return ugly[n - 1];
}

如果采用逐個(gè)判斷每個(gè)整數(shù)是不是丑數(shù)的解法，直觀但不夠高效，所以我們就需要換一種思路，我的第一反應(yīng)就是這其中一定有什么規(guī)律，但是嘗試著找了一下，沒找到...看了看答案才幡然醒悟，前面提到的算法之所以效率低，很大程度上是因?yàn)椴还芤粋€(gè)數(shù)是不是丑數(shù)，我們都要對(duì)它進(jìn)行計(jì)算，接下來我們?cè)囍业揭环N只計(jì)算丑數(shù)的方法，而不在非丑數(shù)的整數(shù)上花費(fèi)時(shí)間，根據(jù)丑數(shù)的定義，丑數(shù)應(yīng)該是另一個(gè)丑數(shù)乘以2、3或者5的結(jié)果（1除外），因此，我們可以創(chuàng)建一個(gè)數(shù)組，里面的數(shù)字是排好序的丑數(shù)，每個(gè)丑數(shù)都是前面的丑數(shù)乘以2、3或者5得到的，也就是上面的算法了..

295.數(shù)據(jù)流的中位數(shù)（劍指Offer面試題41）

參考答案：（219ms）

public class MedianFinder {

    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        if (minHeap.size() - maxHeap.size() > 0) {
            maxHeap.add(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}

思路：這道題的實(shí)現(xiàn)思路有很多，比如我們可以在插入的時(shí)候就將每個(gè)元素插入到正確的位置上，這樣返回中位數(shù)的時(shí)候就會(huì)是一個(gè)O(1)的操作，下面列舉一張表來說明不同實(shí)現(xiàn)的復(fù)雜度具體是多少：

數(shù)據(jù)結(jié)構(gòu) 插入的時(shí)間復(fù)雜度 得到中位數(shù)的時(shí)間復(fù)雜度
沒有排序的數(shù)組 O(1) O(n)
排序的數(shù)組 O(n) O(1)
排序的鏈表 O(n) O(1)
二叉搜索樹 平均O(logn)，最差O(n) 平均O(logn)，最差O(n)
AVL樹 O(logn) O(logn)
最大堆和最小堆 O(logn) O(logn)

AVL樹是一種很高效的數(shù)據(jù)結(jié)構(gòu)，但是在大多數(shù)的語言中都沒有現(xiàn)成的實(shí)現(xiàn)，所以考慮用最大堆和最小堆，對(duì)于一個(gè)已經(jīng)排好序的數(shù)據(jù)容器，我們可以從中間分開分成兩個(gè)部分，其中拿P1指向左半部分最大的元素，拿P2指向有半部分最小的元素，如果能夠保證數(shù)據(jù)容器左邊的數(shù)據(jù)都小于右邊的數(shù)據(jù)，那么即使左、右兩邊內(nèi)部的數(shù)據(jù)沒有排序，我們?nèi)匀豢梢愿鶕?jù)左邊最大的數(shù)和右邊最大的數(shù)得到中位數(shù)：



如何快速從一個(gè)數(shù)據(jù)容器中找出最大數(shù)呢？我們可以使用最大堆來實(shí)現(xiàn)這個(gè)數(shù)據(jù)容器，因?yàn)槎秧數(shù)脑鼐褪亲畲蟮脑兀煌瑯游覀兛梢允褂米钚《褋砜焖僬页鲆粋€(gè)數(shù)據(jù)容器中最小數(shù)。因此按照這個(gè)思路我們就可以使用一個(gè)最大堆實(shí)現(xiàn)左邊的數(shù)據(jù)容器，使用一個(gè)最小堆實(shí)現(xiàn)右邊的數(shù)據(jù)容器，但是需要注意的是這兩個(gè)容器的大小差值不能超過1；

347. 前K個(gè)高頻元素（類似劍指Offer面試題40）

參考答案：（131ms）

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<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(map::get));
    for (int key : map.keySet()) {
        if (pq.size() < k) {
            pq.add(key);
        } else if (map.get(key) > map.get(pq.peek())) {
            pq.remove();
            pq.add(key);
        }
    }

    LinkedList<Integer> res = new LinkedList<>();
    while (!pq.isEmpty()) {
        res.add(pq.remove());
    }
    return res;
}

692. 前K個(gè)高頻單詞

參考答案：（72ms）

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap();
    for (String word: words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    List<String> candidates = new ArrayList(count.keySet());
    Collections.sort(candidates, (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
            w1.compareTo(w2) : count.get(w2) - count.get(w1));

    return candidates.subList(0, k);
}

這道題類似于上面的第347題，但是問題出在返回的順序上，需要自己來定義一個(gè)比較器來排序..然后也學(xué)到一個(gè)寫法，就是上面的第一個(gè)for循環(huán)里，getOrDefault()方法，get√..

參考答案2：（91ms）

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap();
    for (String word: words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    PriorityQueue<String> heap = new PriorityQueue<String>(
            (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
                    w2.compareTo(w1) : count.get(w1) - count.get(w2) );

    for (String word: count.keySet()) {
        heap.offer(word);
        if (heap.size() > k) heap.poll();
    }

    List<String> ans = new ArrayList();
    while (!heap.isEmpty()) ans.add(heap.poll());
    Collections.reverse(ans);
    return ans;
}

這個(gè)解法就有點(diǎn)兒類似于上面的347題，其實(shí)是大同小異，就是自己不會(huì)靈活使用比較器而已，學(xué)習(xí)到了學(xué)習(xí)到了√...

簡(jiǎn)單總結(jié)

今天算是很有收獲的一天，因?yàn)檫@兩種數(shù)據(jù)結(jié)構(gòu)都是自己特別不熟悉的，特別是在刷了一些LeetCode相關(guān)題目之后，對(duì)這兩種數(shù)據(jù)有了很不一樣的認(rèn)識(shí)，特別是堆的應(yīng)用，這是一種特別適合用來找第k小/大的特殊的數(shù)據(jù)結(jié)構(gòu)，并且在Java中居然有直接的實(shí)現(xiàn)，這可太棒了，而且今天的效率還算挺高的，滿足；

歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處！
簡(jiǎn)書ID：@我沒有三顆心臟
github：wmyskxz
歡迎關(guān)注公眾微信號(hào)：wmyskxz_javaweb
分享自己的Java Web學(xué)習(xí)之路以及各種Java學(xué)習(xí)資料

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容