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

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小的数字。

那么得想想其他办法，比如说二分，但是该二分什么呢，一下子很难想到，一般情况下都是二分给定的数据中有的数字，但是这儿行不通。
后来想到了可以直接二分答案，尽管这个答案不在生成的数列中。
我们可以用二分逼近。
二分一个答案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))
完美的复杂度

https://blog.csdn.net/u011846436/article/details/38468555
1.对两数组分别进行排序。
2.使用剪切法，如果a[i]+b[j]>val,则a[i]+b[j+1],a[i]+b[j+2]...a[i]+b[n]均大于val;反之，则说明数组a选取第i个元素作为左加数后，数组b中有j个元素可以作为右加数，能够使a[i]+b[0...j]<=val。
3.对i进行遍历，则可以确定值val在合并后的数组C中排名（很关键）。
4.采用二分法，求出中值mid在合并后的数组中排名，如果mid的排名>k，说明排第k位的数在mid左侧；否则，去右侧查找

05	typedef long long lld;

06	const lld M = 100001;

07	lld arr1[M],arr2[M];

08	lld m,n,k;

09

10	//统计小于等于 mid 的个数

11	lld cntMin(lld mid){

12	lld cnt = 0;

13	lld j = n-1;

14	for(int i=0; i<m; i++){

15	//由于已排序，可直接利用上一次结果

16	while(j >= 0 && arr1[i] + arr2[j] > mid) j--;

17	cnt += j+1;

18

}

19	return cnt;

20

}

21

22	lld low,high,mid;

23	int main() {

24	freopen("in.txt", "r", stdin);

25	while(scanf("%lld%lld%lld", &m,&n,&k) != EOF){

26	for(lld i=0; i<m; i++) scanf("%lld", &arr1[i]);

27	for(lld j=0; j<n; j++) scanf("%lld", &arr2[j]);

28	sort(arr1, arr1+m);

29	sort(arr2, arr2+n);

30	low  = arr1[0] + arr2[0];

31	high = arr1[m-1] + arr2[n-1];

32

lld ans;

33

//二分逼近

34	while(low <= high){

35	mid = (low+high)/2;

36	lld cnt = cntMin(mid);

37	if(cnt >= k){

38	ans = mid; //mid有可能是解

39	high = mid-1;

40

}else

41	low = mid+1;

42

}

43	printf("%lld\n",ans);

44

45

}

46

return 0;

47

}