LeetCode 优先级队列（堆）章节

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 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]，这就是最后剩下那块石头的重量。

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

int lastStoneWeight(vector<int>& stones) {priority_queue<int> pq;for (int i : stones) {pq.push(i);}while (pq.size() > 1) {int y = pq.top();pq.pop();int x = pq.top();pq.pop();int tmp = y - x;if (tmp)pq.push(tmp);}return pq.empty() ? 0 : pq.top();
}

设计一个找到数据流中第 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]

解释：

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 次

// 小根堆
priority_queue<int, vector<int>, greater<int>> pq;
int k;KthLargest(int k, vector<int>& nums) {this->k = k;for (int i : nums)pq.push(i);
}int add(int val) {pq.push(val);while (pq.size() > k)pq.pop();return pq.top();
}

给定一个单词列表 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] <= 10
• words[i] 由小写英文字母组成。
• k 的取值范围是 [1, 不同 words[i] 的数量]

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

哈希 + 优先级队列

大根堆，时间复杂度： O(nlogn)，空间复杂度：O(n)。

struct cmp {bool operator()(const pair<string, int>& a, const pair<string, int>& b) {if (a.second < b.second)return true;if (a.second == b.second && a.first > b.first)return true;return false;}
};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string, int> hash;for (string& str : words)hash[str]++;// 大根priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;for (auto& p : hash)pq.push(p);vector<string> ans;while(k--) {auto p = pq.top();pq.pop();ans.push_back(p.first);}return ans;
}

C++11代码优化，小根堆优化时间复杂度和空间复杂度。

小根堆，时间复杂度： O(nlogk)，空间复杂度：O(k)。

vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string, int> hash;for (string& str : words)hash[str]++;auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) {return a.second == b.second ? a.first < b.first : a.second > b.second;};// 小根priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> pq;for (auto& p : hash) {pq.emplace(p);if (pq.size() > k)pq.pop();}vector<string> ans(k);for (int i = k - 1; i >= 0; --i) {ans[i] = pq.top().first;pq.pop();}return ans;
}

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

• 例如 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

提示:

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

• que_min 是大根堆，用于存储数据流中较小的一半元素，堆顶元素是较小的一半元素中最大的元素。
• que_max 是小根堆，用于存储数据流中较大的一半元素，堆顶元素是较大的一半元素中最小的元素。

priority_queue<int, vector<int>, less<int>> que_min; // 大根堆
priority_queue<int, vector<int>, greater<int>> que_max; // 小根堆MedianFinder() {}void addNum(int num) {if (que_min.empty() || num <= que_min.top()) {que_min.push(num);if (que_min.size() > que_max.size() + 1) {que_max.push(que_min.top());que_min.pop();}} else {que_max.push(num);if (que_max.size() > que_min.size()) {que_min.push(que_max.top());que_max.pop();}}
}double findMedian() {if (que_min.size() > que_max.size())return que_min.top();return (que_min.top() + que_max.top()) / 2.0;
}