ac_786第k个数

题目描述

题目大意&链接

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

输入输出样例：
输入:

5 3
2 4 1 5 3

输出：

3

详情：ac_786第k个数

解题思路

这题是在快排算法上的pro版，需要你在每排序完一次，都需要与 k 做个判断：数列的哪边继续递归排序。

1. 定义 <= x 的一边元素数量为s1：

   int s1 = j - l + 1;

2. 当 k <= s1 时，递归排序数列的左边；否则递归排序数列的右边

   if(k <= s1) return quick_sort(l, j, k);
   else return quick_sort(j+1, r, k-s1);

3. l == r 时，即代表找到第 k 个排序后的元素

   int quick_sort(int l, int r, int k)
   {
    if(l == r) return q[l];
       ...
    int s1 = j - l + 1;
    if(k <= s1) return quick_sort(l, j, k);
    else return quick_sort(j+1, r, k-s1);
   }

完整代码

#include<iostream>

using namespace std;

const int N = 1e6+10;

int n, k;
int q[N];

int quick_sort(int l, int r, int k)
{
	if(l == r) return q[l];
	
	int x = q[l + r >> 1], i = l - 1, j = r + 1;
	
	while(i < j)
	{
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if(i < j) swap(q[i], q[j]);
	}
	
	int s1 = j - l + 1;
	if(k <= s1) return quick_sort(l, j, k);
	else return quick_sort(j+1, r, k-s1);
}

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

时间和空间复杂度

时间复杂度：O(n) 相比快排省去了递归排序数列两边所耗费的时间
空间复杂度：O(logn) 取决于快速排序形成的递归树调用栈的深度