網易校園招聘筆試題目

1 兩個數組x[]、y[]，長度為n，而且都經過排序從小到大排列，請編寫C/C++程式求出兩個數組合并後（仍然從小到大排列）的中位數，要求比較次數少于n。

分析：要求出中間的兩個數，隻要用一個數組來存儲前面n+1個數就可以了，所求的必然是 第N 和第N+1 個數。

#include<stdio.h>

#include<stdlib.h>

#define N 4

int main()

{

    int i=0,j=0,k=0;

    int a[N]={1,2,3,6};

    int b[N]={7,8,90,99};

    int c[N+1];

    for(k=0;k<=N&&i<N&&j<N;k++)//當k>N跳出循環，此時c[1....N] 全部填滿。

    {    if(a[i]<=b[j])

         {           

                       c[k]=a[i];

                       i++;

         }

         else 

           {

                c[k]=b[j];

                 j++;

            }    

      }

  if(i==N&&k<=N) c[N]=b[j];//如果是由于i==N跳出循環，則要考慮到c[N]沒有放資料，是以單獨指派。 

   if(j==N&&k<=N) c[N]=a[i];

    printf("%d,%d",c[N-1],c[N]);

    system("pause");

}