Google面试题 数组中第K小的数目字 九度oj 1534

Google面试题 数组中第K小的数字 九度oj 1534

#include<iostream>#include<stdio.h>#include<cstring>#include<math.h>#include<algorithm>using namespace std;int a[100005],b[100005];long long m,n,k;int judge(long long mi,long long k){long long i,j sum=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)return 1;//就把范围扩大1/4继续寻找，直到找到 }return 0;}int main(){int i; long long R,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);}return 0;}