[Lc14_priority_queue] 最后一塊石頭重量 | 數據流中的第 K 大元素 | 前K個高頻單詞

1.最后一塊石頭的重量

題解

2.數據流中的第 K 大元素

題解

3.前K個高頻單詞

題解

代碼

?4.數據流的中位數

題解

在C++中，使用標準庫中的priority_queue，默認情況下它是一個最大堆（即大堆排序），這意味著最大的元素總是位于隊列的前面。具體來說，默認使用的比較器是std::less<T>

1.最后一塊石頭的重量

鏈接：1046. 最后一塊石頭的重量

有一堆石頭，每塊石頭的重量都是正整數。

每一回合，從中選出兩塊 最重的 石頭，然后將它們一起粉碎。假設石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結果如下：

如果 x == y，那么兩塊石頭都會被完全粉碎；
如果 x != y，那么重量為 x 的石頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。

最后，最多只會剩下一塊石頭。返回此石頭的重量。如果沒有石頭剩下，就返回 0。

示例：

輸入：[2,7,4,1,8,1]
輸出：1
解釋：
先選出 7 和 8，得到 1，所以數組轉換為 [2,4,1,1,1]，
再選出 2 和 4，得到 2，所以數組轉換為 [2,1,1,1]，
接著是 2 和 1，得到 1，所以數組轉換為 [1,1,1]，
最后選出 1 和 1，得到 0，最終數組轉換為 [1]，這就是最后剩下那塊石頭的重量。

題解

每一回合，從中選出兩塊最重的石頭，x == y，那么兩塊石頭都會被完全粉碎；
如果 x != y，那么重量較小的 x 石頭將會完全粉碎，而重量較大的 y 的石頭新重量為 y-x。
最多只會剩下一塊石頭。

返回此石頭的重量。如果沒有石頭剩下，就返回 0。

每次挑選的是先挑一堆數中最大的那個數，然后再挑一個剩下數中最大的數。

這不正好符合大根堆的數據結構嗎。

解法：用堆來模擬這個過程

先拿數組的數創建一個大根堆，每次從堆里面選擇最大和次大兩個數

如果相等就是0不用加入到大根堆里
如果不相等用最大的數減去次大的數，把結果加入到堆里面。

如果最后堆里還剩下一個數，返回這個數。如果堆為空說明石頭全都粉碎了返回0即可。

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;for(auto& n:stones)heap.push(n);while(heap.size()>1){int n1=heap.top();heap.pop();int n2=heap.top();heap.pop();if(n1==n2) continue;else{int tmp=n1>n2?n1-n2:n2-n1;heap.push(tmp);}}return heap.empty()?0:heap.top();   }
};

2.數據流中的第 K 大元素

鏈接：703. 數據流中的第 K 大元素

設計一個找到數據流中第 k 大元素的類（class）。注意是排序后的第 k 大元素，不是第 k 個不同的元素。

請實現 KthLargest 類：

KthLargest(int k, int[] nums) 使用整數 k 和整數流 nums 初始化對象。
int add(int val) 將 val 插入數據流 nums 后，返回當前數據流中第 k 大的元素。

示例 1：

輸入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

輸出：[null, 4, 5, 5, 8, 8]

題解

設計一個找到數據流中第 k 大元素的類（class）。

注意是排序后的第 k 大元素，不是第 k 個不同的元素。

int add(int val) 將 val 插入數據流 nums 后，返回當前數據流中第 k 大的元素。

這道題其實考察的是一個非常經典的問題， TopK問題。

關于TopK問題有兩種解題思路，一種是堆 O(nlogk)，一種是前面剛學的快速選擇算法 O(n)（前文回顧：[Lc7_分治-快排] 快速選擇排序 | 數組中的第K個最大元素 | 庫存管理 III。
快速選擇排序雖然快，但是對于海量的數據內存根本放不下。
所以在海量數據情況最優的還是堆。

解法：用堆來解決

創建一個大小為 k 的堆（大根堆 or 小根堆）
循環

1.依次進堆
2.判斷堆的大小是否超過 K

在堆的實現，畫圖和代碼分析建堆，堆排序，時間復雜度以及TOP-K問題，對于求第K個最大元素

我們也是將前K個數建個小堆，然后將剩下的N-K個元素和堆頂元素做比較
如果大于堆頂元素，就先把棧頂元素pop掉，也就是把堆中最小元素刪除，然后將它放進去。
這樣一直循環，直到所有元素都比較完成。

因為是一直把堆中最小的pop掉，那堆的元素就是N個元素中最大的，而堆頂就是第K個最大的元素

別忘記我們這是一個小堆！

sum: eg. TOP_K 大，建一個 K 小堆，大于 top 就 pop,push, 最后的就是第 K 大了，因為是一個數值為 K 的小堆

這里我們也是建小堆，依次進堆，當堆大小超過K個，pop堆頂元素，把堆中最小元素pop掉，并且使堆保持K個大小。

每次都是堆中最小元素去掉。那最后堆中剩下的就是前K個最大元素，而堆頂就是第K個最大元素。

考慮一下下面兩個問題

用大根堆還是小根堆
為什么要用大根堆（小根堆）

class KthLargest {
public:priority_queue<int,vector<int>,greater<int>> heap;int _k;KthLargest(int k, vector<int>& nums) {//第k大，建小堆_k=k;for(auto& num:nums){heap.push(num);if(heap.size()>k) heap.pop();//刪除最小的}}int add(int val) {heap.push(val);if(heap.size()>_k) heap.pop();//刪除最小的return heap.top();}
};

3.前K個高頻單詞

鏈接：692. 前K個高頻單詞

給定一個單詞列表 words 和一個整數 k ，返回前 k 個出現次數最多的單詞。

返回的答案應該按單詞出現頻率由高到低排序。如果不同的單詞有相同出現頻率， 按字典順序 排序。

示例 1：

輸入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
輸出: ["i", "love"]
解析: "i" 和 "love" 為出現次數最多的兩個單詞，均為2次。注意，按字母順序 "i" 在 "love" 之前。

示例 2：

輸入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
輸出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出現次數最多的四個單詞，出現次數依次為 4, 3, 2 和 1 次。

題解

這是一個TopK的問題，注意，返回的答案應該按單詞出現頻率由高到低排序。

如果不同的單詞有相同出現頻率，按字典順序(由低向高) 排序。

解法：利用 “堆” 來解決 TopK 問題

1. 預處理一下原始的字符串數組：用一個哈希表，統計一下每一個單詞出現的頻次。

2. 創建一個大小為 k 的堆，類提供的比較函數滿足不了要求，我們要自己定義一個！

（返回的答案應該按單詞出現頻率由高到低排序。如果不同的單詞有相同出現頻率，按字典順序(由低向高) 排序。）

如果比較頻次創建一個小根堆，如果比較字典序(頻次相同的時候)，創建一個大根堆。

所以說創建堆寫比較函數的時候必須要考慮這兩點

當頻次相同的時候字典序按照大根堆方式比較
當頻次不同的時候按照小根堆方式比較。

3. 循環

1.依次進堆

2.判斷堆的大小是否超過 K

4. 提取結果
因為求前K大，所以建的是一個小根堆，然后提取堆頂元素在pop是一個升序的。
逆序一下取前K個

代碼

#和 ds 討論后的優化代碼，用lambda和emplace

?4.數據流的中位數

鏈接：295. 數據流的中位數

中位數是有序整數列表中的中間值。如果列表的大小是偶數，則沒有中間值，中位數是兩個中間值的平均值。

例如 arr = [2,3,4] 的中位數是 3 。
例如 arr = [2,3] 的中位數是 (2 + 3) / 2 = 2.5 。

實現 MedianFinder 類:

MedianFinder() 初始化 MedianFinder 對象。
void addNum(int num) 將數據流中的整數 num 添加到數據結構中。
double findMedian() 返回到目前為止所有元素的中位數。與實際答案相差 10-5 以內的答案將被接受。

示例 1：

輸入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
輸出
[null, null, null, 1.5, null, 2.0]解釋
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

題解

給一個數據流，讓返回每次當前已經加入到數組的數據流的中位數。

中位數是有序整數列表中的中間值。

如果列表的大小是偶數，則沒有中間值，中位數是兩個中間值的平均值。
表的大小是奇數，直接返回中間的數。

解法一：直接sort

每次從數據流中來一個數插入數組中之后，都對當前數組進行sort

然后通過下標的方式找到中間數。

每次add加入一個數都要sort，時間復雜度是O(nlogn)。

總體時間復雜度是非常恐怖的。
因為是下標訪問，find 時間復雜度是 O(1)

解法二：插入排序的思想

[0,end] 有序，插入 end + 1，使 [0, end + 1]有序。

這道題正好就是這樣的思想。

相當于打撲克，找到合適的位置。

add函數，每次插入一個數的時候都需要從后往前掃描找一個插入的位置

因此時間復雜度是O(n)
find 也是通過下標去找時間復雜度是O(1)

解法三：大小堆來維護數據流的中位數

此時有一個數軸已經按照從小到大的排好序了，這個時候想找中間數的時候。

把這些數的前半部分放到一個大根堆里面，后半部分放到小根堆里面。
此時找中間值也很快，前面較小的數放到大根堆里面，堆頂元素是數軸中這些較小元素種最右邊的值。
后面較大的數放到小根堆里面，堆頂元素是數軸中這些較大元素最左邊。

此時我們僅需根據數組中的元素的個數就可以求出中位數是多少了。

如果數組是偶數

大根堆和小根堆正好把數軸平分
然后大堆堆頂元素和小堆堆頂元素相加 /2就是這個數組的中位數。

如果數組是奇數個。

我們就先人為規定一下，數軸左邊元素是m個，右邊是n個
人為規定左邊大根堆多方一個元素，m > n (m = n + 1)
此時中位數就是左邊大根堆的堆頂元素。

向這樣用大根堆存左邊較小部分，小根堆存右邊較大部分。

find 時間復雜度也是O(1)，而add快了很多
因為我們是從堆存這些元素的，插入和刪除每次調整堆僅需O(logn)

細節問題：

add如何實現：

假設現在有兩個堆了。
一個大根堆left，一個小根堆right。
left元素個數m個，right元素個數n個，left堆頂元素x，right堆定元素y。

如果此時來了一個數num，num要么放在left里，要么放在right里。

但是放好之后可能會破壞之前的規則：

m == n
m > n —> m == n + 1

我們必須維護上面的規則，才能正確找到數組中位數。

接下來分情況討論：

m == n

num要么插入left，要么插入right。

如果num要進入left，那么num <= x，但是別忘記 m == n 有可能兩個堆全為空，num也是直接進入left。
此時 m 比 n 多了一個。沒關系直接進就行。

如果num進入right，那條件是 num > x。

此時就有問題了。n > m了，而 n > m是不被允許的，所以我們要把右邊堆調整一下，就是拿right堆頂元素放到left里。
因為right是一個小根堆，堆頂就是最小值。
拿到left，還是能保證left堆里元素是較小的，right堆里元素是較大的。
拿right堆頂元素放到left里正好滿足 m == n + 1。

這里有一個細節問題，必須num先進right堆，然后再拿right堆定元素放到left

因為 x < num < y，如果直接把y拿過去了，就破壞了left都是較小元素。right都是較大元素。

m > n —> m == n + 1

如果num進入left，那么num <= x ，但是此時不滿足 m == n + 1

因此進棧后將棧頂元素給right。
如果num進入right，那么num > x , m == n了，直接進就行了

注意：上面都是 先進棧再拿棧頂移動

順便復習了大頂堆小頂堆，紅黑樹，avl樹，排序。很好的題

class MedianFinder {
private:std::priority_queue<int> left;    // 大頂堆存較小的一半std::priority_queue<int, std::vector<int>, std::greater<int>> right; // 小頂堆存較大的一半public:MedianFinder() {}  // 構造函數不需要初始化隊列void addNum(int num) {int m=left.size();int n=right.size();if(m==n){if(m==0 || num<=left.top())//注意為空left.push(num);else{right.push(num);left.push(right.top());right.pop();}}if(m>n){if(num<=left.top()){left.push(num);right.push(left.top());left.pop();}//先 進棧 再拿棧頂移動elseright.push(num);}}double findMedian() {if(left.size() > right.size()) {return left.top();}return (left.top() + right.top()) / 2.0;  // 2.0確保浮點運算}
};