AcWing 786.第K个数

给定一个长度为 n 的整数数列，以及一个整数 k，请求出数列从小到大排序后的第 k 个数。

输入格式

输入共两行，第一行包含整数 n 。

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

输出格式

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

数据范围

1 ≤ n ≤ 100000

1 ≤ k ≤ n

输入样例：

1
2
5 3
2 4 1 5 3

输出样例：

1
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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int l , int r){
    // 区间大小为1，跳出循环
    if(l >= r) return;
    // 一开始 左边是 -1 右边是 length, pivot不取第一个元素是避免出现极端情况退化成单链表
    int i = l - 1 , j = r + 1 , pivot = q[(l + r) >> 1];
    while(i < j){
        do j--; while(q[j] > pivot);
        do i++; while(q[i] < pivot);
        if(i < j) swap(q[i],q[j]);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);
}

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

技术支持

我