寻找Kth数

题目描述:

输入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

---

来源: 原创