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左侧；否则，去右侧查找
给定两个整型数组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 | } |
