【算法题攻略】优先级队列（堆）

一、题目解析

1. 数据流中的第 K 大元素（TOP-K问题）

703. 数据流中的第 K 大元素

• 题目描述：

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

（1）KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
（2）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 ]
• 解释：
  KthLargest kthLargest = new KthLargest( 3, [4, 5, 8, 2] );
  kthLargest.add(3); // 返回 4
  kthLargest.add(5); // 返回 5
  kthLargest.add(10); // 返回 5
  kthLargest.add(9); // 返回 8
  kthLargest.add(4); // 返回 8

示例 2：

• 输入：
  [ “KthLargest”, “add”, “add”, “add”, “add” ]
  [ [4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9] ]
• 输出：[ null, 7, 7, 7, 8 ]
• 解释：
  KthLargest kthLargest = new KthLargest( 4, [7, 7, 7, 7, 8, 3] );
  kthLargest.add(2); // 返回 7
  kthLargest.add(10); // 返回 7
  kthLargest.add(9); // 返回 7
  kthLargest.add(9); // 返回 8

提示：

• 0 <= nums.length <= 10^4
• 1 <= k <= nums.length + 1
• -10^4 <= nums[i] <= 10^4
• -10^4 <= val <= 10^4
• 最多调用 add 方法 10^4 次

• 代码演示：

classKthLargest{int_k;// 维持一个元素个数最大为_k的小堆// 当元素个数为_k时，第_k大的元素就是堆顶元素priority_queue<int,vector<int>,greater<int>>pri;public:KthLargest(intk,vector<int>&nums){_k=k;for(autoit:nums){if(pri.size()<_k)pri.push(it);else{if(it>pri.top()){pri.push(it);pri.pop();// 维持小堆的元素个数为_K}}}}intadd(intval){if(pri.size()<_k)pri.push(val);else{if(val>pri.top()){pri.push(val);pri.pop();// 维持小堆的元素个数为_K}}// 根据题目提示：1 <= k <= nums.length + 1// 推断在小堆插入一次元素后，小堆元素个数绝对稳定在_k个returnpri.top();}};/** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */

2. 前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 次。

注意：

• 1 <= words.length <= 500
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成。
• k 的取值范围是 [1, 不同 words[i] 的数量]

进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

• 代码演示：

classSolution{public:classgreater{public:booloperator()(pair<string,int>&pa1,pair<string,int>&pa2){if(pa1.second==pa2.second)// 当不同的单词有相同出现频率{returnpa1.first<pa2.first;// 字符串比较 按照大堆排序(也就是 字典序按照小堆排序)}returnpa1.second>pa2.second;// 单词出现频率 按照小堆排序}};vector<string>topKFrequent(vector<string>&words,intk){// 统计每种单词出现的次数unordered_map<string,int>hash;for(autoword:words)hash[word]++;// 维持k个元素数量的小堆priority_queue<pair<string,int>,vector<pair<string,int>>,greater>pri;for(autopair_word:hash){pri.push(pair_word);if(pri.size()>k){pri.pop();}}// 提取结果vector<string>vec_str(k," ");for(inti=k-1;i>=0;i--){vec_str[i]=pri.top().first;pri.pop();}returnvec_str;}};

3. 数据流的中位数（利用两个堆）

295. 数据流的中位数

• 题目描述：

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

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

实现 MedianFinder 类:

（1）MedianFinder() 初始化 MedianFinder 对象。
（2）void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
（3）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

提示:

• -10^5 <= num <= 10^5
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 10^4 次调用 addNum 和 findMedian

• 代码实现：

classMedianFinder{public:// 左侧大根堆priority_queue<int,vector<int>,less<int>>pri_left;// 左侧小根堆priority_queue<int,vector<int>,greater<int>>pri_right;MedianFinder(){}voidaddNum(intnum){if(pri_left.size()==pri_right.size()){if(pri_left.size()==0)pri_left.push(num);else{if(num<=pri_left.top())pri_left.push(num);else{pri_right.push(num);pri_left.push(pri_right.top());pri_right.pop();}}}else{if(num>pri_left.top())pri_right.push(num);else{pri_left.push(num);pri_right.push(pri_left.top());pri_left.pop();}}}doublefindMedian(){doublemid;if(pri_left.size()==pri_right.size())mid=(pri_left.top()+pri_right.top())/2.0;elsemid=pri_left.top();returnmid;}};/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */