AcWing 786. 第k个数
原题链接
简单
作者:
墨墨
,
2022-02-25 22:45:47
,
所有人可见
,
阅读 166
本题与快排共同点:定边界并递归处理子问题。不同点在于此题需要通过判断轮排之后,第k小的数在较大区间还是较小区间,然后只递归处理所在区间就可以了,这样就会把时间复杂度降为O(n).
int quick_sort(int l,int r,int k)
{
if(l == r) return q[l];
//考虑问题一定要考虑全面,在操作始终保持有效下,要注意只有一个元素的情况,这也是递归处理的最后一环。
int i = l - 1 , j = r + 1 , x = q[l + r >> 1];
while(l < r)
{
do i ++ ;while(q[i] < x);
do j -- ;while(q[j] > x);
if(i < j) swap(q[i],q[j]);
}
int sum = j - l + 1;
if(sum >= k) return quick_sort(l,j,k); //递归处理子问题
return qucik_sort(j + 1,r,k -sum1); //递归处理子问题
}