快速选择第k个数

题目描述

给定一个序列，求第k小的数

算法思想

利用快速排序思想，算法复杂度能达到O（n）步骤如下：

1.找到排序分界点x，这里选择区间最左值

2.排序，让左边的值都小于x，右边都大于x

3.递归排序寻找数字，如果左区间数字数目大于k，直接在左边找第k小的数字，如果左区间数字数目小于k，则在右边找

模板

#include<bits/stdc++.h>

using namespace std;

int n, k;

const int maxn = 1e5 + 10;

int a[maxn];

int quickSort(int l, int r, int k) {

    if (l == r) return a[l];

    int x = a[l], i = l - 1, j = r + 1;

    while (i < j) {

        while (a[++i] < x);

        while (a[--j] > x);

        if (i < j) swap(a[i], a[j]);

    }

    int ls = j - l + 1;

    if (k <= ls) return quickSort(l, j, k);

    return quickSort(j + 1, r, k - ls);

}

int main() {

    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    cout << quickSort(0, n - 1, k);

    return 0;

}

巴特西

快速选择第k个数

快速选择第k个数

题目描述

算法思想

模板

最新文章

热门文章

巴特西

快速选择 第k个数

快速选择 第k个数

题目描述

算法思想

模板

最新文章

热门文章

快速选择第k个数

快速选择第k个数