题目:
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time
complexity should be O(log (m+n)).
complexity should be O(log (m+n)).
思路:
基本思路是从两个数组中依次移除最小最大的一对数,重复操作直到两个数组共剩下1个或者2个数,即为中位数。
代码:
class Solution { public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int left_A = 0; int right_A = m-1; int left_B = 0; int right_B = n-1; while((right_A>=left_A||right_B>=left_B)&&(getNum(left_A,right_A)+getNum(left_B,right_B))>2) { getMinVal(left_A,right_A,A)<getMinVal(left_B,right_B,B)?left_A++:left_B++; getMaxVal(left_A,right_A,A)<getMaxVal(left_B,right_B,B)?right_B--:right_A--; }; if(left_A==right_A&&left_B==right_B) { return (A[left_A]+B[left_B])/2.0; } else if(left_A==right_A) { return A[left_A]; } else if(left_B==right_B) { return B[left_B]; } else if(left_A+1==right_A) { return (A[left_A]+A[right_A])/2.0; } else if(left_B+1==right_B) { return (B[left_B]+B[right_B])/2.0; } } int getMinVal(int left, int right, int array[]) { if(left>right) return INT_MAX; else return array[left]; } int getMaxVal(int left, int right, int array[]) { if(left>right) return INT_MIN; else return array[right]; } int getNum(int left, int right) { if(left>right) { return 0; } else { return right-left+1; } } };