本文主要是介绍找第K大数(ACdream 1099),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
瑶瑶的第K大
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
Sample Input
5 2 5 4 1 3 1
Sample Output
4
Hint
Source
Manager
读入要优化,否则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 xxzfreopen("in.txt","r",stdin);#endif // xxzn = input();k = input();for(int i = 1; i <= n; i++) a[i] = input();printf("%d\n",solve(1,n));return 0;
}
利用STL实现
#include<iostream>
#include <algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cstdio>
using namespace std;
const int N = 11111111;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;
}
这篇关于找第K大数(ACdream 1099)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!