(找第k大的数)给定一个长度为1,000,000的无序正整数序列, 以及另一个数n (1<=n<=1000000), 然后以类似快速排序的方法找到序列中第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(void) % (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(void) { 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; }