前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >ACdream 1099 瑶瑶的第K大

ACdream 1099 瑶瑶的第K大

作者头像
全栈程序员站长
发布2022-07-12 16:57:31
2700
发布2022-07-12 16:57:31
举报

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

瑶瑶的第K大

Time Limit: 10000/5000MS (Java/Others)Memory Limit: 512000/256000KB (Java/Others)

SubmitStatisticNext Problem

Problem Description

一天,萌萌的妹子–瑶瑶(tsyao)非常无聊,就来找你玩。但是你们都不知道玩什么。。。尴尬了一阵子,机智的瑶瑶就提议:“这样吧,你说N个整数xi,然后在任意说一个数字k,我可以高速地说出这些数字里面第 k 大的数字。”

Input

第1行 两个整数N, K以空格隔开;

第2行 有N个整数(可出现相同数字,均为随机生成),相同以空格隔开。

0 < n ≤ 5*10^6 , 0 < k ≤ n

1 ≤ xi ≤ 10^8

Output

输出第 k 大的数字。 Sample Input

5 2 5 4 1 3 1 Sample Output

4 Hint

如2,2,1中三个数字中第一大数字为2,第二大数字也为2,第三大数字为1 。

闲来无聊,静静心,刷刷水题,突然想起快排的实现过程还不懂,于是就找到了这个题,专研了快排,也算懂个所以然了!

只是这个题做得纠结啊,卡超时卡得太紧了,还得优化输入,无奈啊!!

AC代码例如以下:

代码语言:javascript
复制
#include<iostream>
#include<cstring>
#include<cstdio>
#define M 6000010
using namespace std;

int num[M];

int input()
{
    int ans=0;
    char a;
    while((a=getchar())<'0'||a>'9');
    ans=a-'0';
    while((a=getchar())>='0'&&a<='9')
    {
        ans=ans*10+a-'0';
    }
    return ans;
}

int qsort(int l,int r,int k)
{
    if(l==r)
        return num[l];
    int i,j,a;
    a=num[l];i=l;j=r;
    while(i<j)
    {
        while(i<j&&num[j]<=a)
            j--;
        if(i<j)
            num[i++]=num[j];
        while(i<j&&num[i]>=a)
            i++;
        if(i<j)
            num[j--]=num[i];
    }
    num[i]=a;
    if(i==k) return num[i];
    else if(i>k) return qsort(l,i-1,k);
        else return qsort(i+1,r,k);
}


int main()
{
    int i,j;
    int n,k;
    n=input();k=input();
    for(i=1;i<=n;i++)
        num[i]=input();
    int ans=qsort(1,n,k);
    printf("%d\n",ans);
    return 0;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/118702.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021年12月,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档