找第k大的数
Description
给定一个长度为1,000,000的无序正整数序列，以及另一个数n(1<=n<=1000000)，接下来以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）。Input Format
#include <cstdio>
#include <cstdlib>
int a[1000001], ans = -1;
void swap(int *a, int *b) {
int c;
c = *a; *a = *b; *b = c;
}
int FindKth(int left, int right, int n) {
int tmp, value, i, j;
if (left == right) return left;
tmp = rand() % (right - left) + left;
swap(&a[tmp], &a[left]);
value = __[1]__
i = left;
j = right;
while (i < j) {
while (i < j && __[2]__) j--;
if (i < j) { a[i] = a[j]; i++; }
else break;
while (i < j && __[3]__) i++;
if (i < j) { a[j] = a[i]; j--; }
else break;
}
__[4]__
if (i < n) return FindKth(__[5]__);
if (i > n) return __[6]__
return i;
}
int main() {
int i,n;
int m = 1000000;
for (i = 1; i <= m; i++)
scanf("%d", &a[i]);
scanf("%d", &n);
ans = FindKth(1, m, n);
printf("%d\n", a[ans]);
return 0;
}
Output Format
只需输出答案即可，一共6行，每行一个大写字母Hint
Source
排序相关
在下列比赛中: