AcWing 786.第k个数

2021-01-14 11:20

阅读：414

标签：swa 遍历 swap printf 输入格式 int 数列 -- 描述

AcWing 786.第k个数

题目描述

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

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~10^9
范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第k小数。

数据范围

1≤n≤100000,
1≤k≤n

输入样例

5 3
2 4 1 5 3

输出样例

题目思路

使用快速选择算法，在快排的基础上进行优化，达到O(N),
每次只需要遍历1/2个长度

#include
using namespace std;
const int N = 1e5+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(ix);
        if(isl)
        return quick_sort(j+1,r,k-sl);
    return quick_sort(l,j,k);
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i

AcWing 786.第k个数

标签：swa 遍历 swap printf 输入格式 int 数列 -- 描述

原文地址：https://www.cnblogs.com/fsh001/p/12263077.html

上一篇：最简单的密码验证asp.net c#

下一篇：上传文件asp.net c#

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

亲，登录后才可以留言！

AcWing 786.第k个数

AcWing 786.第k个数

题目描述

输入格式

输出格式

数据范围

输入样例

输出样例

题目思路

评论

热门文章

推荐文章

最新文章

置顶文章