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)


相关推荐

  • IOS越狱学习总结

    IOS越狱学习总结iOS越狱iOS越狱(iOSJailbreaking),是用于获取苹果公司便携装置操作系统iOS最高权限的一种技术手段,用户使用这种技术及软件可以获取到iOS的最高权限,甚至可能可以进一步解开运营商对手机网络的限制。中文名称iOS越狱外文名称iOSJailbreaking应  用电子产品类  型软件目录1简介2用途3针对的设备

  • 重复读取输入流_redis同时读写

    重复读取输入流_redis同时读写inputstream只能读取一次,再次读取则无法获取到内容。这是因为inputStream的内部有个pos指针,当读取的时候指针会不断的移动,当移动到末尾的时候,就无法再次读取了。问题解决:方法一:使用ByteArrayOutputStream将字节缓存,每次读取都从ByteArrayOutputStream里面获取。获取ByteArrayOutputStream…

  • xshell7怎么连接虚拟机_centos ssh

    xshell7怎么连接虚拟机_centos ssh文章目录一、xshell简介二、xshell安装三、xshell链接虚拟机的centos71.查看虚拟机中centos系统的ip2.利用ip链接一、xshell简介Xshell[1]是一个强大的安全终端模拟软件,它支持SSH1,SSH2,以及MicrosoftWindows平台的TELNET协议。Xshell通过互联网到远程主机的安全连接以及它创新性的设计和特色帮助用户在复…

  • 10行代码集2000张美女图,Python爬虫120例,再上征途[通俗易懂]

    10行代码集2000张美女图,Python爬虫120例,再上征途[通俗易懂]Python爬虫120例,又来啦

  • mySQL插入数据自动生成时间

    mySQL插入数据自动生成时间

  • 深度学习 | Word2vec原理及应用

    深度学习 | Word2vec原理及应用聊聊Word2vec1前言2什么是Word2vec?2.1定义2.1.1分词的原理介绍2.1.2文本向量化的方式2.2数学原理2.2.1CBOW(ContinuousBag-of-Words)原理2.2.2Skip-Gram原理2.2.3为什么要有Word2vec而不是用原来的?2.2.4Word2vec基础:霍夫曼树2.2.5HierarchicalSoftmax2….

发表回复

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

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