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]<valueif (i < j) {a[i] = a[j]; i ++;} else break;while (i < j && [ ③ ]) i ++;//a[i]>valueif (i < j) {a[j] = a[i]; j - -;} else break;}[ ④ ] //a[i]=valueif (i < n) return FindKth([ ⑤ ] );//i+1,right,nif (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]
2.正确答案： 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++版）在线评测系统
CSP-J1 CSP-S1 第1轮 初赛 集训视频集（2022.08.22）
CSP-J1 CSP-S1 第1轮 初赛 集训视频集（2022.08.22）-CSDN博客
CSP-J1 CSP-S1 信奥 第1轮 初赛 数据分析 成绩及分数线汇总
CSP-J1 CSP-S1 信奥 第1轮 初赛 数据分析 成绩及分数线汇总-CSDN博客
2019-2021 CSP-J CSP-S 第一轮成绩及分数线汇总
2019-2021 CSP-J CSP-S 第一轮成绩及分数线汇总-CSDN博客
CSP-J CSP-S 初赛相关的书籍
CSP-J CSP-S 初赛相关的书籍_csp带什么书_dllglvzhenfeng的博客-CSDN博客
CSP-J1 CSP-S1 第1轮 初赛 考前强化训练
CSP-J1 CSP-S1 第1轮 初赛 考前强化训练-CSDN博客