您的位置: 首页  >  IT文章  >  Google面试题 数组中第K小的数目字 九度oj 1534

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

分类: IT文章 • 2023-12-27 12:44:43
Google面试题 数组中第K小的数字 九度oj 1534
题目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>
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;
			else	L=mid;
		}
		printf("%lld\n",L);
	}
	return 0;
}



相关推荐