题目描述

给你一个长度为n的序列，求序列中第k小数的多少。

输入描述:

多组输入，第一行读入一个整数T表示有T组数据。
每组数据占两行，第一行为两个整数n，k，表示数列长度和k。
第二行为n个用空格隔开的整数。

输出描述:

对于每组数据，输出它的第k小数是多少。
每组数据之间用空格隔开。

示例

输入

2
5 2
1 4 2 3 4
3 3
3 2 1

输出

2
3

方法一 ： 堆排序（或称优先队列）

基础知识

运用堆在解决实际问题的时候通常可分为大顶堆与小顶堆，堆顶始终维护堆中最大/最小的元素，而堆内部不一定有序，堆排序的时间复杂度在O(nlogn)量级

本题解法

本题要求元素序列中的第k小的数，则堆中需维护最小的k个数，采用大顶堆
用cnt来记录当前堆中的元素个数（也可以使用pq.size()这个stl的内置函数，pq是我初始化的堆名）

• 当cnt < k时，直接将当前元素放入堆中
• 当cnt >= k时，取出堆顶元素e，与当前元素比较，若e<=当前元素则不进行操作，若e>当前元素则将e弹出，将当前元素压入堆中
• 最终堆顶留下来的元素即为第k小数

具体代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

int T;

void solve(){
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, less<int>> pq; 
    int cnt = 0;
    for (int i = 0; i < n; i++){
        int now;
        cin >> now;
        if (cnt < k) {
            pq.push(now);
            cnt++;
        }
        else{
            if (pq.top() > now){
                pq.pop();
                pq.push(now);
            }
        }
    }
    cout << pq.top() << endl;
}

signed main(){
    ios :: sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin >> T;
    while (T--){
        solve();
    }
    return 0;
}

方法二 ： 优化版快速排序（更快）

基础知识

快速排序本身是一种基于双指针和分治思想的排序方法，在每一趟排序中至少可以确定一个元素的最终位置，若我使用pivot来表示这个位置，则每次可返回一个数组下标来表示本轮排序中被确定的元素在什么地方

快排模板

int partition(int low, int high, int a[]){
	int pivot = a[low]; // 每次取当前待排区间的第一个元素做本轮的待排元素
    while (low < high){
    	while (a[high] >= pivot && low < high) high--;
        a[low] = a[high];
        while (a[low] >= pivot && low < high) low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}
void quickSort(int low, int high, int a[]){
	if (low >= high) return; // 当前待排序元素为1或0时不需要排序直接返回
    int mid = (low + high) / 2;
    int pivot = partition(low, high, a); // pivot位置已确定
    quickSort(low, pivot - 1, a); // pivot左侧排序
    quickSort(pivot + 1, high, a); // pivot右侧排序
}

改进方法

从上面一段代码可以看出，其实在每一轮排序的过程中已经生成了已排序元素的最终位置并返回了回来，那么我们只需要判断当前排好序的这个元素的下标是不是k就行，记这个下标为pivot

• 若pivot == k，则找到了第k小的元素，直接返回当前元素即可
• 若pivot > k，说明第k小的元素在pivot左边，对pivot左侧区间进行排序即可
• 若pivot < k, 说明第k小的元素在pivot右边，对pivot右侧区间进行排序即可

具体代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5000010;
int a[N];
int T;

inline int read(){ // 快读模板，用普通scanf或者cin也能ac，无需纠结这块
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int partition(int l, int r){
    int pivot = a[l];
    while (l < r){
        while (a[r] >= pivot && l < r) r--;
        a[l] = a[r];
        while (a[l] <= pivot && l < r) l++;
        a[r] = a[l];
    }
    a[l] = pivot;
    return l;
}

void quickSort(int l, int r, int k){  // 只改了这个地方
    if (l >= r) return;
    int pivot = partition(l, r);
    if (pivot == k) return;
    else if (pivot > k) quickSort(l, pivot - 1, k);
    else quickSort(pivot + 1, r, k);
}

void solve(){
    int n, k;
    n = read();
    k = read();
    for (int i = 0; i < n; i++){
        a[i] = read();
    }
    quickSort(0, n - 1, k - 1);
    cout << a[k - 1] << endl;
}

signed main(){
    cin >> T;
    while (T--){
        solve();
    }
    return 0;
}