ACdream 1099 瑶瑶的第K大

ACdream 1099 瑶瑶的第K大

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

瑶瑶的第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代码例如以下:

#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;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 前端面试:浅拷贝和深拷贝的区别是什么_java中的浅拷贝和深拷贝

    前端面试:浅拷贝和深拷贝的区别是什么_java中的浅拷贝和深拷贝浅拷贝(shallowcopy):只复制指向某个对象的指针,而不复制对象本身,新旧对象共享一块内存;  深拷贝(deepcopy):复制并创建一个一摸一样的对象,不共享内存,修改新对象,旧对象保持不变。…

  • robotium android,Robotium 测试Android apk安装包

    robotium android,Robotium 测试Android apk安装包介绍要测试apk程序必须和我们编写的测试程序拥有相同的签名(signature)。如果没有apk程序的签名秘钥,就要去除apk程序的签名,然后再使用自己的key对其签名(这一步中,我们可以使用debugkey),已经有现成的工具可用,下载地址re-sign.jar,这个工具可以去掉apk程序的原签名,然后使用我们自己的debugkey对其签名。详细编写测试用例之前,我们需要知道apk程序的包名…

  • J1939 多包报文传输

    J1939 多包报文传输以J1939RC(RetarderConfigration)报文为例,19个字节,需要分3条报文发送。1、将要发送多包报文之前先会广播一条ID为0x18ECFF**形式的一条报文TPCM(以目前理解最后**为源地址,RC报文的话为0F),数据场会提示接下来将会发送多少条报文,包含什么信息(RC)。2、随后以一条ID为0x18EB00**形式TPDT发送3条报文,传输数据多于8字节的报文…

  • idea中创建一个web项目

    idea中创建一个web项目第一步:新建空的java项目在idea项目下,新建一个model,这个model就可以是一个java项目。然后会弹出一个框,选择新建java项目:点击【next】之后进入下一步,取model项目名称:写好名称和存放的路径之后,点击【finish】完成java的model项目创建:以上就是一个空的java项目的创建。第二步:在java项目的基础上创建web项目右击刚创建的java项目,添加web项目所需架构,如下图:点击【AddFrameworksSupport】之后,会弹出一个

  • JB全家桶 激活码_在线激活

    (JB全家桶 激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • js 正则替换换行符

    js 正则替换换行符vardiv=document.getElementById(‘div’);vars=div.innerHTML.replace(/(\n|\r|(\r\n)|(\u0085)|(\u2028)|(\u2029))/g,””);//g的意思是:执行全局匹配(查找所有匹配而非在找到第一个匹配后停止)。//取消了空格之后在做其他的替换才可以,否则不能替换

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号