hihoCoder 1133-二分·二分查找之k小数 #1133 : 二分·二分查找之k小数 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在上一回里我们知道Nettle在玩《艦これ》，Nettle的镇守府有很多船位，但船位再多也是有限的。Nettle通过捞船又出了一艘稀有的船，但是已有的N(1≤N≤1,000,000)个船位都已经有船了。所以Nettle不得不把其中一艘船拆掉来让位给新的船。Nettle思考了很久，决定随机选择一个k，然后拆掉稀有度第k小的船。 已知每一艘船都有自己的稀有度，Nettle现在把所有船的稀有度值告诉你，希望你能帮他找出目标船。 提示：非有序数组的二分查找之二 输入 第1行：2个整数N,k。N表示数组长度， 第2行：N个整数，表示a[1..N]，保证不会出现重复的数，1≤a[i]≤2,000,000,000。 输出 第1行：一个整数t，表示t在数组中是第k小的数，若K不在数组中，输出-1。 样例输入 10 4 1732 4176 2602 6176 1303 6207 3125 1 1011 6600 样例输出 1732
给定一个无序序列，问序列中第k小的数是哪个。简单粗暴的方法是排序直接取a[k]，复杂度为O(nlgn)；还有一种O(lgn)的方法，采用了和hihoCoder 1128-二分·二分查找类似的方法，将序列不断二分成小于某个数和大于某个数的两部分，直到某一部分长度为k。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; int n, k; vector<int> a; int GetNumberK(int p, int q) { int m = a[p], i = p, j = q; while (i < j) { while (i < j&&a[j] > m) j–; a[i] = a[j]; while (i < j&&a[i] < m) i++; a[j] = a[i]; } if (k == i + 1)//(1) return m; else if (k < i + 1) return GetNumberK(p, i – 1); else { //k = k – (i – p + 1);//(2)，因为(1)处判等的时候i取p，但分割之后p并没有从0开始，所以k还是k return GetNumberK(i + 1, q); } } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); a.resize(n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); if (k > n||k < 1) printf("-1\n"); else printf("%d\n", GetNumberK(0, n – 1)); return 0; } [/cpp] 本代码提交AC，用时69MS，内存3MB。 需要注意一点，代码中(2)不能出现，虽然递归在[i+1,q]内部查找第k – (i – p + 1)小的数，但是(1)处判等的时候，使用的i（即p）是相对[0,n-1]长度的，所以这里的k不需要剪短]]>