我是靠谱客的博主 安静睫毛,这篇文章主要介绍活用双指针快排求第k大值AcWing 786. 快排应用——第k个数 原题链接 简单,现在分享给大家,希望可以做个参考。

AcWing 786. 快排应用——第k个数 原题链接 简单

题目描述
给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列的第k小的数是多少。

输入格式
第一行包含两个整数 n 和 k。

第二行包含 n 个整数(所有整数均在1~109范围内),表示整数数列。

输出格式
输出一个整数,表示数列的第k小数。

数据范围
1≤n≤100000,
1≤k≤n

输入样例
5 3
2 4 1 5 3
输出样例
3
算法1
快速选择算法
快排的每一趟,数轴的左边都会是 <= x 的, 右边都是 >= x 的。
左边元素的个数是 s1 = j - l + 1, 如果k <= s1 的话,那么下次递归的区间就是左边,否则右边。
直到 l == r 时返回q[l]。

时间复杂度
O(n)

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream> using namespace std; const int N = 1e5 + 5; long long a[N]; int q[N]; //双指针寻找第k大值 int quick_sort(int l , int r, int k){ if(l == r) return q[l]; int x = q[l], i = l - 1, j = r + 1;//以最左边第一个元素作为划分值对数组排序,左边的必须小于它,右边必须大于它 while(i < j){ while(q[++i] < x);//直到左边出现大于x的数 while(q[--j] > x);//直到右边出现小于x的数 if(i < j) swap(q[i], q[j]);//交换两个数,俗称:归位! } //以x为划分值得数组已经排序完毕,此时j >= i; int s1 = j - l + 1;//左区间的最后一个位置 if(k <= s1) quick_sort(l, j, k);//如果k值比最后一个位置小,则应该在左边继续排序 else quick_sort(j+1 , r , k - s1);//如果k值比最后一个位置大,则应该在右边继续排序 //但是这里必须注意此时所要求的排序位置应该应该变为右边区间的第k-s1小 } int main(){ long long n, m; cin >> n >> m; for(int i = 0; i < n; i++) scanf("%d", &q[i]); cout << quick_sort(0, n - 1, m) << endl; }

最后

以上就是安静睫毛最近收集整理的关于活用双指针快排求第k大值AcWing 786. 快排应用——第k个数 原题链接 简单的全部内容,更多相关活用双指针快排求第k大值AcWing内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(99)

评论列表共有 0 条评论

立即
投稿
返回
顶部