hihoCoder 1133-二分·二分查找之k小数

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。

完整代码如下:

#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;
}

本代码提交AC,用时69MS,内存3MB。

需要注意一点,代码中(2)不能出现,虽然递归在[i+1,q]内部查找第k - (i - p + 1)小的数,但是(1)处判等的时候,使用的i(即p)是相对[0,n-1]长度的,所以这里的k不需要剪短

Leave a Reply

Your email address will not be published. Required fields are marked *