题库 信息学奥赛题库 题目列表 完善程序:(找第 k 大的数) 给定一个长度为 106 的...
组合题

完善程序:

(找第 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; }

第 1 题 填空
第 2 题 填空
第 3 题 填空
第 4 题 填空
第 5 题 填空
第 6 题 填空
题目信息
完善程序 2008年 初赛
-
正确率
0
评论
60
点击