完善程序:
(找第 k 大的数) 给定一个长度为 106 的无序正整数序列, 以及另一个数
n(1≤n≤106), 然后以类似快速排序的方法找到序列中第 n 大的数(关于第 n 大的数:例如序列 {1,2,3,4,5,6} 中第 3 大的数是 4)。
#include <iostream> using namespace std; 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 =[ ① ]; i = left; j = right; while (i < j) { while (i < j && [ ② ]) j --; if (i < j) {a[i] = a[j]; i ++;} else break; while (i < j && [ ③ ]) i ++; if (i < j) {a[j] = a[i]; j - -;} else break; } [ ④ ] if (i < n) return FindKth([ ⑤ ] ); if (i > n) return [ ⑥ ] return i; } int main() { int i; int m = 1000000; for (i = 1;i <= m;i ++) cin >> a[i]; cin >> n; ans = FindKth(1,m,n); cout << a[ans]; return 0; }