找第K大数(ACdream 1099)

发布时间：2020-12-14 02:31:40 所属栏目：大数据来源：网络整理

导读：瑶瑶的第K大 Time Limit:?4000/2000MS (Java/Others) ? Memory Limit:?256000/128000KB (Java/Others) Submit? Statistic? Next Problem Problem Description 一天，萌萌的妹子--瑶瑶(tsyao)很无聊，就来找你玩。可是你们都不知道玩什么。。。尴尬了一阵子，

瑶瑶的第K大

Time Limit:?4000/2000MS (Java/Others)? Memory Limit:?256000/128000KB (Java/Others)

Submit? Statistic? Next 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

Hint

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

Source

tsyao

Manager

tsyao

读入要优化，否则TLE

1:STL函数实现

2：快排思想实现

#include <bits/stdc++.h>
#define N 6000010
int a[N];
int n,k;

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 solve(int l,int r)
{
    if(l == r) return a[l];
    int i = l,j = r,temp = a[l];
    if(l < r)
    {
        while(i < j)
        {
            while(i < j && a[j] < temp) j--;
            if(i < j) a[i++] = a[j];
            while(i < j && a[i] > temp) i++;
            if(i < j) a[j--] = a[i];
        }
        a[i] = temp;
        if(i == k) return a[i];
        else if(i < k)  solve(i+1,r);
        else solve(l,i-1);
    }
}

int main()
{
    #ifdef xxz
    freopen("in.txt","r",stdin);
    #endif // xxz
    n = input();
    k = input();
    for(int i = 1; i <= n; i++) a[i] = input();
    printf("%dn",solve(1,n));
    return 0;
}

利用STL实现

#include<iostream>
#include <algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cstdio>
using namespace std;
const int N = 22222111;
 void scan_d(int &ret)
{
    char c;
    ret = 0;
    while((c=getchar())<'0' || c>'9');
    while(c>='0'&&c<='9') ret = ret*10 +(c-'0'),c=getchar();
}
int a[N];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i = 0 ; i<n;i++)
    {
           scan_d(a[i]);
    }
 
    nth_element(a,a+n-k,a+n);
    cout<<a[n-k]<<endl;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!