堆
分为大顶堆和小顶堆：特点是一个完全二叉树，根节点总是比左右两个子节点大（小）。
建立堆时 需要解决两个问题：
- 从无序的数中建立堆
- 当取出堆顶元素后如何调整堆
先解决第二个问题， 如上图所示， 取出堆顶元素后， 将尾部元素插到顶部，调整即可。</p> 对于第一个问题， 其实就是一个对多个元素调整的问题。我们需要先从最后一个非叶节点调整，依次调整至堆顶节点。优先队列就是基于堆的结构实现的。
215. Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example, Given [3,2,1,5,6,4] and k = 2, return 5.
Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.
思路：可以建立一个小顶堆， 维护最大的k 个元素。 那么第k 大个元素就在堆顶了。 我们需要建立个k大小的堆，然后再向里面加元素的时候，与堆里顶元素即最小元素比较大小，如果堆顶元素小，那么淘汰堆顶，讲较大的元素入堆。这样遍历一遍，我们就淘汰了最小的 n-k个元素。 时间复杂度为 nlogk
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int> > q;
for(int i = 0; i < nums.size(); i++){
if(q.size() == k){
if(q.top() < nums[i]){
q.pop();
q.push(nums[i]);
}
}else{
q.push(nums[i]);
}
}
return q.top();
}
};
第二种解法： 用快排的思想
int findKthLargest(vector<int>& nums, int k) {
const int size_n = nums.size();
int left = 0, right = size_n;
while (left < right) {
int i = left, j = right - 1, povit = nums[left];
while(i <= j) {
while (i <= j && nums[i] >= povit) i++;
while (i <= j && nums[j] < povit) j--;
if (i < j)
swap(nums[i++], nums[j--]);
}
swap(nums[left], nums[j]);
if (j == k - 1) return nums[j];
if (j < k - 1) left = j + 1;
else right = j;
}
}
int findKthLargest(vector<int>& nums, int k) {
int head = 0;
int tail = nums.size() - 1;
int low, high;
while(1){
low = head;
high = tail;
int p = nums[low];
while(low < high){
while((low < high) && nums[high] >= p){
high --;
}
if(low < high){
nums[low++] = nums[high];
}
while((low < high) && nums[low] < p){
low++;
}
if(low < high){
nums[high--] = nums[low];
}
}
if((tail - low + 1) == k){
return p;
}else if((tail - low + 1) > k){
head = low + 1;
}else{
k = k - (tail - low + 1);
tail = low - 1;
}
}
return -1;
}
23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
思路: 对每个链表，从头结点开始建立一个堆，然后每次都弹出最小的插入新链表的结点，然后将此结点的后一个节点入堆 .(在处理链表问题， 经常用一个冗余节点做头结点， 然后返回其next)
class Solution {
public:
struct compare {
bool operator()(const ListNode* l, const ListNode* r) {
return l->val > r->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> q;
for(int i = 0; i < lists.size(); i++){
if(lists[i]){
q.push(lists[i]);
}
}
ListNode* dummy = new ListNode(-1);
ListNode* c = dummy;
while(!q.empty()){
c->next = q.top();
q.pop();
c = c->next;
if(c->next){
q.push(c->next);
}
}
return dummy->next;
}
};
378. Kth Smallest Element in a Sorted Matrix
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13.
思路： 这个题可以用二分查找来做。另外用堆的性质也可以做。观察一下，其实和上题的多个有序链表合并类似。这个矩阵是每行都有序的。 我们也从每行的头开始，入堆。但是矩阵元素并不和链表节点一点可以根据一个节点直接找到下一个节点。所以我们可以自己定义一个结构体，或用 pair<int, pair<int, int» 表示元素和其下一个元素的位置。循环k 次， 每次从堆里弹出最小的，就能找到 kth element
class Solution {
public:
struct compare
{
bool operator()(const pair<int,pair<int, int> >& a, const pair<int,pair<int, int> >& b)
{
return a.first>b.first;
}
};
int kthSmallest(vector<vector<int>>& arr, int k) {
int n=arr.size(),m=arr[0].size();
priority_queue< pair<int,pair<int, int> >, vector<pair<int, pair<int, int> > >, compare > p;
for(int i=0;i<n;i++)
p.push(make_pair(arr[i][0],make_pair(i,0)));
int x=k -1,ans;
while(x--)
{
int ans=p.top().first;
int i=p.top().second.first;
int j=p.top().second.second;
p.pop();
if(j!=m-1)
p.push(make_pair(arr[i][j+1],make_pair(i,j+1)));
}
return p.top().first;
}
};
373. Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.
Example 1: Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6] 思路： 注意数组是有序的，可以不用都遍历 m*n, 每次保证最小的元素在堆里， 然后再把可能的最小元素入堆。
class Solution {
struct compare
{
bool operator()(const pair<int , pair<int, int> >& a, const pair< int, pair<int, int> >& b)
{
return a.first > b.first;
}
};
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
if((nums1.size() * nums2.size()) == 0 || k == 0){
return vector<pair<int, int> >();
}
//其实两个数组 第k 后的元素都不用管了
priority_queue<pair<int, pair<int, int> > , vector<pair<int, pair<int, int> >>, compare> q;
for(int i = 0; i < min(k, (int)nums1.size()); i++){
q.push(make_pair(nums1[i] + nums2[0], make_pair(i, 0)));
}
vector<pair<int, int> > result;
for(int i = 0 ; i < k && !q.empty(); i++){
pair<int, int> index = q.top().second;
q.pop();
result.push_back(make_pair(nums1[index.first], nums2[index.second]));
if(index.second < nums2.size() - 1){
q.push(make_pair(nums1[index.first] + nums2[index.second + 1], make_pair(index.first, index.second + 1)));
}
}
return result;
}
};
239. Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max ————— —– [1 3 -1] -3 5 3 6 7 | 3
| 1 [3 -1 -3] 5 3 6 7 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 7 |
Therefore, return the max sliding window as [3,3,5,5,6,7].
解法一： 用双端队列。遍历数组。我们在双端队列维护后边可能用到的最大值。队列的元素是存的数组下标（便于比较位置） 。 每到达一个新位置， 我们会把队列从后往前遍历， 如果队列的元素比此位置的小， 那么删除。然后把新位置入队列（因为后边的滑动窗口可能用到此位置的值，即使它比队列里的元素小）。 例外要处理一下，滑动到一定时候，将不在窗口范围内的队列的front 元素删掉。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> buffer;
vector<int> maxs;
for(int i = 0; i < nums.size(); i++){
while(!buffer.empty() && nums[i] >= nums[buffer.back()]){
buffer.pop_back();
}
buffer.push_back(i);
if( i >= k -1){
maxs.push_back(nums[buffer.front()]);
}
if(buffer.front() <= i - k + 1){
buffer.pop_front();
}
}
return maxs;
}
};
解法二：使用最大堆，每次找到窗口最大的输出，但是一个棘手的问题是，我们怎么移除已不在滑动窗口的元素呢？ 同样，我们不能只将元素值存储，还有存元素的位置。移除最前面的元素很困难。但是我们可以再每次在新窗口插新元素的时候，检查最大的值是否已经溢出窗口，如果溢出了那么移除他。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
if (k == 0) return result;
priority_queue<pair<int, int>> w;
int n = (int)nums.size();
for (int i = 0; i < n; i++) {
while (!w.empty() && w.top().second <= i-k)
w.pop();
w.push(make_pair(nums[i],i));
if (i >= k-1)
result.push_back(w.top().first);
}
return result;
}
};
347. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].
思路： 遇到这种求前K 大（小）的题目 都会想到堆。这个题我们要建堆的对象是数字出现的频率，并且返回的是数字。所以堆的元素需要一个pair的结构。 对数字频率的统计可以用hash表。 对前K个词频大的数字维护一个K大小的小根堆，遍历一遍数字，把更小的pop 和前面的题目类似的思想。
class Solution {
public:
struct compare
{
bool operator()(const pair<int, int>& a, const pair<int, int>& b)
{
return a.first>b.first;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++){
map[nums[i]] ++;
}
unordered_map<int, int>::iterator it;
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> q;
for(it = map.begin(); it!=map.end(); it++ ){
if(q.size() < k || q.top().first < it->second){
pair<int, int> pp = make_pair(it->second, it->first);
if(q.size() >= k && q.top().first < it->second){
q.pop();
}
q.push(pp);
}
}
vector<int> r(k);
for(int i = 0; i < k; i++){
r[k - i - 1] = (q.top().second);
q.pop();
}
return r;
}
};
解法二： bucket sort 。 hash 求到每个num 的频率后， 根据频率建立bucket. 比如频率为3 的数字有[5,6,9]..然后从后往前遍历bucket, 就是频率从大到小的
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
for (int num : nums)
++m[num];
vector<vector<int>> buckets(nums.size() + 1);
for (auto p : m)
buckets[p.second].push_back(p.first);
vector<int> ans;
for (int i = buckets.size() - 1; i >= 0 && ans.size() < k; --i) {
for (int num : buckets[i]) {
ans.push_back(num);
if (ans.size() == k)
break;
}
}
return ans;
}
};
451. Sort Characters By Frequency
Input: “tree”
Output: “eert”
思路： 和上个题一样， hashtable + 优先队列 或者 bucket sort 都可以
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> map;
priority_queue<pair<int, char>> q;
for(int i = 0; i < s.length(); i++){
map[s[i]]++;
}
for(auto it = map.begin(); it != map.end(); it++){
q.push(make_pair(it->second, it->first));
}
string r = "";
while(q.size()){
pair<int, char> p = q.top();
for(int j = 0; j < p.first; j++){
r += p.second;
}
q.pop();
}
return r;
}
};
313. Super Ugly Number
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note: (1) 1 is a super ugly number for any given primes. (2) The given numbers in primes are in ascending order. (3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000. (4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
struct Node {
int val,index,prime;
Node(int index,int val,int prime):index(index),val(val),prime(prime){}
bool operator < (const Node &b)const {
return val > b.val;
}
};
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector <int> ugly_nums(n, 0);
ugly_nums[0] = 1;
priority_queue<Node> q;
for (int j = 0; j < primes.size(); j++) {
q.push(Node(0, primes[j], primes[j]));
}
for (int i = 1; i < n; i++) {
Node cur = q.top();
ugly_nums[i] = cur.val;
do {
cur = q.top(); q.pop();
cur.val = cur.prime * ugly_nums[++cur.index];
q.push(cur);
} while (!q.empty() && q.top().val == ugly_nums[i]);
}
return ugly_nums[n - 1];
}
};
