Google面试题 数组中第K小的数字

题目1534：数组中第K小的数字

时间限制：2 秒

内存限制：128 兆

特殊判题：否

提交：682

解决：105

题目描述：

给定两个整型数组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

来源：

Google面试题

看这道题就要知道一定不能用一般的方法做，因为不能存放那么大的数组，这里用二分法，并且只要找的次数就可以与 k进行比较

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<algorithm>
usingnamespacestd;
inta[100005],b[100005];
longlongm,n,k;
intjudge(longlongmi,longlongk)
{
longlongi,jsum=0;
j=n-1;

for(i=0;i<m;i++)
{
while(a[i]+b[j]>mi&&j>=0)j--;


if(j<0)break;
sum=sum+j+1;//这里利用每次比中值小的数组的个数来表示
//要比每次都加1好如果从中间值找不到k个数
if(sum>=k)return1;//就把范围扩大1/4继续寻找，直到找到
}
return0;
}
intmain()
{
inti;
longlongR,L,mid;
while(scanf("%lld%lld%lld",&m,&n,&k)!=EOF)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(i=0;i<m;i++)scanf("%d",&a[i]);
for(i=0;i<n;i++)scanf("%d",&b[i]);
sort(a,a+m);
sort(b,b+n);
L=a[0]+b[0];
R=a[m-1]+b[n-1];
while(L<R)
{
mid=(L+R+1)/2;
if(judge(mid-1,k))R=mid-1;
elseL=mid;
}
printf("%lld\n",L);
}
return0;
}