NOIP 2008 普及组初赛试题完善程序 4.2 （找第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()% (right - left) + left;


swap(a[tmp],a[left]);


value =[ ① ];//a[left]

i = left;

j = right;

while (i < j)

{

while (i < j && [ ② ]) j --;// a[j]<value

if (i < j)

{

a[i] = a[j];

i ++;

}

else break;


while (i < j && [ ③ ]) i ++;//a[i]>value

if (i < j) {a[j] = a[i]; j - -;} else break;

}

[ ④ ] //a[i]=value

if (i < n) return FindKth([ ⑤ ] );//i+1,right,n

if (i > n) return [ ⑥ ] // FindKth(left,i–1,n);

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.正确答案： a[left]
.正确答案： a[j]<value
3.正确答案： a[i]>value
4.正确答案： a[i]=value;
5.正确答案： i+1,right,n
6.正确答案： FindKth(left,i–1,n);
【NOIP2011】13．在含有n个元素的双向链表中查询是否存在关键字为k的元素，最快情况下运行的时间复杂度是（    ）。
         A．O(1 )            B．O( log n )        

        C．O( n )            D．O( n log n )

P1923 【深基9.例4】求第 k 小的数
【深基9.例4】求第 k 小的数 - 洛谷



1235：输出前k大的数
信息学奥赛一本通（C++版）在线评测系统


《聪明人的游戏 信息学探秘.提高篇》 第四章 简单排序(C++) 第2课 考试排名——插入排序（Score）《聪明人的游戏 信息学探秘.提高篇》 第四章 简单排序(C++) 第2课
信息学奥赛研究1：竞赛时间表、学习规划信息学奥赛研究1：竞赛时间表、学习规划