AcWing 786. 第k个数
宋标 Lv5
  2022-08-18 02:31:32 2022-08-18 02:31    

题目

给定一个长度为 的整数数列，以及一个整数 ，请用快速选择算法求出数列从小到大排序后的第 个数。

输入格式

第一行包含两个整数 和 。

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

输出格式

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

数据范围

,

输入样例：

5 3
2 4 1 5 3

输出样例：

3

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int a[N];
int n, k;

/**
 *  i, j是随着数组边界一直在变化，所以不需要特殊处理
 *  只需要对左边界或左边界排序取决于k所在的位置
 */
int q_sort(int l, int r)
{
    if (l >= r) return a[l];

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

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

    if (j >= k) return q_sort(l, j);
    else q_sort(j + 1, r);
}

int main()
{
    cin >> n >> k;

    -- k;

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

    cout << q_sort(0, n - 1) <<  endl;

    return  0;
}
 评论