google 笔试题两个n维数组logn求中位数问题

两个n维数组，已排序，为升序。设计算法求2n的数中第n大的数。要求分析时间和空间复杂度。

 

 比较两个有序表各自的中位数 a，b 假设 a>=b,那么这2n个数的中位数一定不在第一个序列>a的那部分上，因为第一个序列中有n/2-1个数比a小，第二个序列中至少有n/2个数比a小(a>=b)，同理，中位数一定不在第二个序列

 

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 5

#define MAX(a,b) (a)>(b)?(a):(b)

void print_arrat(int A[], int n)
{
  int i;
  for(i=0;i<n;i++)
   printf("%d\t",A[i]);
   
   printf("\n");
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int partition(int A[], int start, int end)
{
  int x = A[end];
  int i = start-1;
  int j = start;
  
  for(;j<end;j++)
   {
     if(A[j]<x)
      {
        i++;
        swap(A+i, A+j);
      }
   }
   swap(A+i+1, A+end);
   
   return i+1;
}

void quick_sort(int A[], int start, int end)
{
  if(start<end)
   {
     int q = partition(A, start, end);
     quick_sort(A, start, q-1);
     quick_sort(A, q+1, end);
   }
}

int count_mid_n(int A[],int a_start,int a_end,int B[],int b_start,int b_end)
{
  int ret = 0;
  if((a_start==a_end)||(b_start==b_end))
  {
    printf("min %d %d\n", A[a_start], B[b_start]);
    ret = MAX(A[a_start], B[b_start]);
    printf("ret is %d\n", ret);
    return ret;
  }
  else
  {
   int a_mid = (a_start+a_end)/2;
   int b_mid = (b_start+b_end)/2;
   printf("a_mid is %d, b_mid is %d\n", A[a_mid], B[b_mid]);
  
   if(A[a_mid]>B[b_mid])
     return count_mid_n(A, a_start,a_mid,B,b_mid,b_end);
   else if(A[a_mid]<B[b_mid])
     return count_mid_n(A, a_mid,a_end,B,b_start,b_mid);
   else
     {
       ret = A[a_mid];
       return ret;
     }
   }
}

int main(int argc, char *argv[])
{
  int i;
  int ret;
  srand((unsigned int)time(NULL));
  int A[N];
  int B[N];
  
  for(i=0;i<N;i++)
   A[i] = rand()%100;
  
  for(i=0;i<N;i++)
   B[i] = rand()%100;
  
  quick_sort(A, 0, N-1);
  quick_sort(B, 0, N-1);
  
  printf("array A is:\n");
  print_arrat(A,N);
  printf("array B is:\n");
  print_arrat(B,N);
  
  ret = count_mid_n(A,0,N-1,B,0,N-1);
  printf("mid of 2n is: %d\n", ret);
  system("PAUSE");    
  return 0;
}


阅读(1646) | 评论(0) | 转发(0) |

0

上一篇：google 笔试题

下一篇：不使用额外空间,将A,B两链表的元素交叉归并