寻找Kth数
提交数: 989, 通过率: 16.99%, 平均分: 48.8
题目描述:
输入n个数,输出第K小的数。
输入格式:
第一行:两个数n和k,用一个空格分隔
接下来n行,每行一个数Ai
输出格式:
一个数,即第k小的数
样例输入:
5 3 2 6 8 3 1
样例输出:
3
提示:
对于30%的数据:n<=10;
对于70%的数据:n<=1,000;
对于100%的数据:n<=10,000,000;0<=Ai<=10^9
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while ( ch < '0' || ch > '9' ) {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
注意,调用sort不行,sort本身效率是O(nlogn),而此题要求的效率必须是O(n)。
时间限制: 1000ms空间限制: 128MB
来源: 原创