视频讲解 – 堆
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int h[N], Size;
// 小根堆
void up(int u) {
while(u/2 > 0 && h[u/2] > h[u]) {
swap(h[u/2], h[u]);
u = u>>1;
}
}
void down(int u) {
while (u < Size) {
int v = u;
if (u * 2 <= Size && h[v] > h[u * 2]) v = u * 2;
if (u * 2 + 1 <= Size && h[v] > h[u * 2 + 1]) v = u * 2 + 1;
if (u == v) break;
swap(h[u], h[v]);
u = v;
}
}
void push(int u) {
h[++Size] = u;
up(Size);
}
int top() {
return Size >= 1 ? h[1] : 0;
}
void pop() {
h[1] = h[Size--];
down(1);
}
int main() {
vector<int> a{3,1,2,4,5};
int n = a.size();
int k = 2; // 第 K 大
// codes...
for (int i = 0; i < n; ++i) {
int t = a[i];
if (Size < k || top() < t) {
push(t);
}
if (Size > k) pop();
}
if (Size == k) {
cout<<top()<<endl;
} else {
cout<<"impossible"<<endl;
}
return 0;
}
视频讲解 – 快速选择
代码
// 找到第 k 大的数,O(n)
#include<bits/stdc++.h>
using namespace std;
vector<int> nums{3,1,2,4,5};
int quick_sort(int l, int h, int k) {
if (l == h) return nums[l];
int i = l - 1, j = h + 1, m = nums[l + h >> 1];
while (i < j) {
while(nums[++i] < m);
while(nums[--j] > m);
if (i < j) swap(nums[i], nums[j]);
}
// l.....j, j+1....h
int lcnt = j-l+1;
if (lcnt >= k) return quick_sort(l, j, k);
else return quick_sort(j+1, h, k-lcnt);
}
int main() {
int k = 4;
int n = nums.size();
k = n - k + 1;
if (k > n) {
cout<<"impossible"<<endl;
} else {
cout<<quick_sort(0, n - 1, k)<<endl;
}
return 0;
}
视频讲解 – 二分搜索
代码
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int l=-1e9,r=1e9,m;
while(l<r) {
m=(l+r+1)>>1;
if(check(nums,k,m)) {
l=m;
} else {
r=m-1;
}
}
return l;
}
bool check(vector<int>& nums, int k, int m) {
int cnt=0;
for (auto&n:nums) if(n>=m) ++cnt;
return cnt>=k;
}
};
参考
[1]. LeetCode 215. 数组中的第K个最大元素. https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-bas-top-k/
2teachers