互联网公司面试题之五
问题:存在两组数组,和4个数字a,b,c,d,要求做如下操作,将第一个数组第a个数到第b个数,第二个数组的第c个数到第d数放到一个数组中,求出合并后数组的中间值,如果有两个中间值,取下标较小的那个。
输入要求:第一行一个整数t表示有t个测试数据,第二行两个整数,表示两个数组的长度,接下来两行表示两个数字的值。最后一行有四个整数a,b,c,d。数组的长度不会超过1000。
输出要求:每行一个整数,对应合并数组的下标在中间的那个值。
性能要求:在时间复杂度O(n)内完成这个计算任务。
答:实现代码如下:
#include <stdio.h>int main(){ int n,a,b,i,k,m,x; int b1,b2,e1,e2; int s[1000],t[1000],p[1000]={0}; for(;~scanf("%d",&n);){ scanf("%d%d",&a,&b); for(i=0;i<a;++i) scanf("%d",&s[i]); for(i=0;i<b;++i) scanf("%d",&t[i]); scanf("%d%d%d%d",&b1,&e1,&b2,&e2); for(k=b1-1,m=0;k<=e1-1;p[s[k++]]=1,++m); for(k=b2-1;k<=e2-1;p[t[k++]]=1,++m); for(k=0,x=0;x<=m/2;k++) if(p[k]==1) ++x; printf("%d\n",--k); }}