用快速排序模板实现查找第k个数

题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。

输入格式
第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第k小数。

数据范围
1≤n≤100000,
1≤k≤n

输入样例

5 3
2 4 1 5 3

输出样例

3

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, k;

int qsort(int l , int r, int k) {
    if((r == n && r - l < 2) || (r < n && r - l < 1))
        return a[l];

    int x = a[(l + r) >> 1];
    int i = l - 1, j = 0;
    (r < n) ? j = r + 1 : j = r;

    while(i < j) {
        while(a[++i] < x);
        while(x < a[--j]);
        if(i < j) swap(a[i], a[j]);
    }

    if(k <= j - l + 1) return qsort(l, j, k);
    if(r == n) return qsort(j, r - 1, k - (j - l + 1) + 1) ;
    else return qsort(j + 1, r, k - (j - l + 1));
}

int main() {
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << qsort(0, n, k);
    return 0;
}

时间复杂度 O(n)

参考文献 大佬yxc的算法视频

C++ 代码

#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
typedef vector<int> vec;
typedef vec::iterator iter;

iter partition(iter& l, iter& r) {
    int p = *(l + rand() % (r - l));
    iter i = l - 1, j = r + 1;
    while(i < j) {
        do ++i; while(*i < p);
        do --j; while(p < *j);
        if(i < j) swap(*i, *j);
    }
    return j;
}

iter quickSort(iter& l, iter& r, int k) {
    if(r - l < 1) return l;
    iter j = partition(l, r);
    int m = j - l + 1, n = k - m;
    if(k <= m) return quickSort(l, j, k);
    else return quickSort(++j, r, n);
}

int solution(iter& lo, iter& hi, int k) {
    srand((unsigned int)(NULL));
    return *quickSort(lo, --hi, k);
}

int main() {
    int n, k;
    cin >> n >> k;
    vec v(n);
    for(auto& x : v) cin >> x;
    iter lo = v.begin(), hi = v.end();
    cout << solution(lo, hi, k) << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> vec;

int quik_search(vec& v, int l, int r, int k) {
    if(l == r) return v[l];

    int x = v[l + ((r - l) >> 1)];
    int i = l - 1, j = r + 1;

    while (i < j) {
        do ++i ; while (v[i] < x);
        do --j ; while (v[j] > x);
        if (i < j) swap(v[i], v[j]);
    }

    // 左边序列的个数：j - l + 1，右边序列的个数：r - (j + 1) + 1
    // 如果左边序列的个数大于等于k，那么第k个数被划分到左边序列中
    // 否则，第k个数被划分到右边序列中，它在右边序列中是第k - (j - l + 1)个数
    if(j - l + 1 >= k) return quik_search(v, l, j, k);
    else return quik_search(v, j + 1, r, k - (j - l + 1));
}

int main() {
    int n, k;
    cin >> n >> k;
    vec v;
    for(int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        v.push_back(t);
    }

    cout << quik_search(v, 0, n - 1, k) << endl;

    return 0;
}