正经题解｜7965.求第 k 小的数

【算法分析】

数据较大，采用分治的思想。
快速排序中，当求出划分后的枢轴位置 $pos$ 后，将数组划分为了 $3$ 个部分，$l$~ $pos-1$、$pos$、$pos+1$~$r$。
如果 $k$ 小于 $pos$，只需对左区间继续划分，
如果 $k$ 大于 $pos$，只需对右区间继续划分，
如果 $k$ 等于 $pos$，$a[k]$ 为第 $k$ 小的数。

【参考代码】

#include <iostream>
using namespace std;

const int N = 5e6 + 10;
int a[N];
int n, k;

int partition(int a[], int l, int r) {
	int m = a[l]; //枢轴
	while (l < r) {
		while (l < r && a[r] >= m) r--;
		a[l] = a[r];
		while (l < r && a[l] <= m) l++;
		a[r] = a[l];
	}
	a[l] = m;
	return l; //返回枢轴位置 
}

//数组 a 的[l,r] 排序(升序） 
void QuickSort(int a[], int l, int r) {
	int pos = partition(a, l, r);//划分后枢轴的位置    划分后将数组分为三块，l~pos-1、pos、pos+1~r 
	if(k < pos) QuickSort(a, l, pos - 1);    //在左边只需搜左区间 
	else if(k > pos) QuickSort(a, pos + 1, r); //在右边只需搜右区间 
	else {  //在中间的话直接输出 
		printf("%d",a[k]);
		return;
	}
}

int main() {
	scanf("%d%d",&n,&k);
	for (int i = 0; i < n; i++) {
		scanf("%d",&a[i]);
	}
	QuickSort(a, 0, n-1);
	return 0;
}

【时间复杂度】

$O(n)$

【预计得分】

$100pts$