786. 第k个数

大佬教程收集整理的这篇文章主要介绍了786. 第k个数，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

快选板子

实际上是在快排板子上改了改

#include <iostream>
using namespace std;

const int n = 100010;

int n, k;
int q[n];

int quick_sort(int l, int r, int k){
    if(l == r) return q[l];
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j){
        do i ++; while(q[i] < X);
        do j --; while(q[j] > X);
        if(i < j) swap(q[i], q[j]);
    }
    
    int sl = j - l + 1;
    if(k <= sl) return quick_sort(l, j, k);
    return quick_sort(j + 1, r, k - sl);
}

int main(){
    cin >> n >> k;
    
    for(int i = 0; i < n; i ++) cin >> q[i];
    cout << quick_sort(0, n - 1, k);
    
    return 0;
}

因为快速排序每一次可以将序列分成两个部分，小的部分和大的部分，设小的部分的长度为L,然后比较k和L的大小，如果k≤L，那么说明第k小数一定在左侧，否则第k小数在右侧并且等价于求右侧的第k-L小数。

复杂度

由于每次只选一边递归下去，所以复杂度每层都会减半

总复杂度为(n+n/2+n/4+...=frac{n(1-(1/2)^k)}{1/2}le 2n=>O(n))

大佬总结

以上是大佬教程为你收集整理的786. 第k个数全部内容，希望文章能够帮你解决786. 第k个数所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。