(找第k大的数) 给定一个长度为1,000,000的无序正整数序列,以及另一个数n(1<=n<=1000000),接下来以类似快速排序的方法找到序列中第n大的数(关于第n大的数:例如序列{1,2,3,4,5,6}中第3大的数是4)。
#include <stdlib.h>
#include <stdio.h>
int a[1000001], n, 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;
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;
}