AcWing 786. 第k个数

2021-01-08 13:29

阅读：617

标签：col tar 大小 lse ret 原理 https 存在全局

原题链接

考察：快速排序

思路：

快速排序的原理是将小于基准点的数全部放在基准点左边,大于全部放在右边,等于随机.我们要找第k小的数,当快速排序把区间一分为2的时候,如果左边的长度>k,说明第k小的数在左边,如果＜说明要找右边找k-cnt(左边的长度)个数.

当我们不断递归的时候,区间会减小通过计算左右区间的长度(因为分好后区间与区间之间有序),我们就能通过区间大小判断k的位置

 1 #include  2 using namespace std;
 3 const int N = 100010;
 4 int k,a[N],n;
 5 int quick_sort(int l,int r,int k)//局部变量覆盖全局变量
 6 {
 7     if(l==r) return a[r];
 8     int x = a[l+r>>1];
 9     int i = l-1; int j = r+1;
10     while(i//当快速排序完成的时候,看是否左边和右边的个数
11         while(a[++i]x);
12         while(a[--j]>x);//存在j超过i的情况
13         if(ij) swap(a[i],a[j]);
14     }
15     int s = j-l+1;
16     if(s>=k) return quick_sort(l,j,k);//通过不断递归,最后区间会被压缩到长度只有1
17     else return quick_sort(j+1,r,k-s);//如果左边数不够,要把前面k-s个更小的元素减去
18 }
19 int main()
20 {
21     scanf("%d%d",&n,&k);
22     for(int i=1;i"%d",&a[i]);
23     printf("%d\n",quick_sort(1,n,k));
24     return 0;
25 }

AcWing 786. 第k个数

标签：col tar 大小 lse ret 原理 https 存在全局

原文地址：https://www.cnblogs.com/newblg/p/14238786.html

上一篇：三、入门案例、MQ标准、API详解

下一篇：windows常用DOS命令

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 786. 第k个数
文章链接：http://soscw.com/index.php/essay/40934.html

亲，登录后才可以留言！

AcWing 786. 第k个数

评论

热门文章

推荐文章

最新文章

置顶文章