小旭讲解 基础算法系列 – 第 K 大的数（Top K）

视频讲解 – 堆

代码

#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/