互联网公司面试题之五

YuHuang.Neil

问题：存在两组数组，和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);        for(i=0;i<b;++i) scanf("%d",&t);        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);    }}

运行结果：