Google 面试题 第K小的数字 二分逼近&二分查找

题目描述：

给定两个整型数组A和B。我们将A和B中的元素两两相加可以得到数组C。
譬如A为[1,2]，B为[3,4].那么由A和B中的元素两两相加得到的数组C为[4,5,5,6]。
现在给你数组A和B，求由A和B两两相加得到的数组C中，第K小的数字。

 

输入：

输入可能包含多个测试案例。
对于每个测试案例，输入的第一行为三个整数m，n， k(1<=m,n<=100000， 1<= k <= n *m)：n，m代表将要输入数组A和B的长度。
紧接着两行， 分别有m和n个数， 代表数组A和B中的元素。数组元素范围为[0,1e9]。

 

输出：

对应每个测试案例，
输出由A和B中元素两两相加得到的数组c中第K小的数字。

 

样例输入：

2 2 3
1 2
3 4
3 3 4
1 2 7
3 4 5

样例输出：

5
6

这个题是把两个数组里面的元素求和后变成新的一个数组C，问数组C中第K大的数字是多少。

题目的数据比较大，最大的K是100000*100000，尽管时限是2秒，但是如果是直接枚举生成前K个数字的话，还是不能通过测试的。

那么得想想其他办法，比如说二分，但是该二分什么呢，一下子很难想到，一般情况下都是二分给定的数据中有的数字，但是这儿行不通。

后来想到了可以直接二分答案，尽管这个答案不在生成的数列中。

我们可以用二分逼近。

二分一个答案X

然后统计一下生成的序列中<=X的有多少个。

如果个数>=K,那么这是一个可能的解，记录一下。

然后我们往小的逼近。

如果<K说明当前的答案不够大。

要往大的逼近。

 

计算比X小的数字有多少个可以利用数组的单调性来做。

先对a,b数字从小到大排序。

然后枚举a中的元素a，统计一下b中有多少个和a加起来是<=X的。

a<=a[i+1]那么b中的符合的个数将会单调不增。

这样验证的复杂度就是O(n+m)了。

最后的总复杂度是O(log(2*10^9)*(n+m))

完美的复杂度。

 

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long lld;
const lld M = 100001;
lld arr1[M],arr2[M];
lld m,n,k;

//统计小于等于 mid 的个数
lld cntMin(lld mid){
	lld cnt = 0;
	lld j = n-1;
	for(int i=0; i<m; i++){
		//由于已排序，可直接利用上一次结果
		while(j >= 0 && arr1[i] + arr2[j] > mid) j--;
		cnt += j+1;
	}
	return cnt;
}

lld low,high,mid;
int main() {
	freopen("in.txt", "r", stdin);
	while(scanf("%lld%lld%lld", &m,&n,&k) != EOF){
		for(lld i=0; i<m; i++) scanf("%lld", &arr1[i]);
		for(lld j=0; j<n; j++) scanf("%lld", &arr2[j]);
		sort(arr1, arr1+m);
		sort(arr2, arr2+n);
		 low  = arr1[0] + arr2[0];
		 high = arr1[m-1] + arr2[n-1];
		 lld ans;
		 //二分逼近
		while(low <= high){
			 mid = (low+high)/2;
			lld cnt = cntMin(mid);
			if(cnt >= k){
				ans = mid; //mid有可能是解
				high = mid-1;
			}else
				low = mid+1;
		}
		printf("%lld\n",ans);

	}
	return 0;
}

 

转自：http://www.acmerblog.com/offer-google-2-1173/