寻找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

来源: 原创