解题思路



假设两个数轴为2个数组

假设长度为N, 那么 中位数一定在 子区间 a 和 c 之间， 继续二分子区间的位置



中位数无非在 区间 a 和 c之间，如何缩小范围呢？


例如：
arr1[1,2,3,4,5]
arr2[3,4,5,6,7]
我们可以看到arr2[2]<arr2[2]，则此时从arr1[0]到arr1[2]这段区间的数是必然比中位数小的。此时 l 则指向位置2即arr[2]=3这个位置。



每次回丢弃掉 数组的一半，推导时间复杂度为 
即

时间复杂度为 o(logN) 

class Solution {
public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * find median in two sorted array
   * @param arr1 int整型vector the array1
   * @param arr2 int整型vector the array2
   * @return int整型
   */

  int findMedianinTwoSortedAray(vector<int> &arr1, vector<int> &arr2) {
    int n = arr1.size(), m = arr2.size();
    if (n != m)
      return -1;
    if(n==0) return 0;
    if(n==1) return min(arr1[0],arr2[0]);
    int l = 0,r =n-1,x=0,y = n-1;
    while(l<r) {
        int even = (r-l) % 2 !=0;//偶数为1，奇数为0 ,例如{0,1} => 1-0=1 % 2 != 0
        int m = l+(r-l)/2;
        int m2 = x+(y-x)/2;
        if(arr1[m] == arr2[m2])
             return arr1[m];
        else if(arr1[m] < arr2[m2]) {
            l = m+even; //长度为偶数的子区间中值后一位才是右半部分的起点
            y = m2;
        }else {
            r = m;
            x = m2 + even;
        }
    }
    return min(arr1[l],arr2[x]);
  }

  int _findMedianinTwoSortedAray(vector<int> &arr1, vector<int> &arr2) {
    // write code here
    int n = arr1.size(), m = arr2.size();
    int total = n + m;
    int K = (total / 2);
    // if(total %2==0) K++;
    // println("K",K);
    //第K个最大数
    priority_queue<int> q;
    int l = 0, r = 0;
    while (q.size() < K) {
      if (arr1[l] <= arr2[r]) {
        q.push(arr1[l++]);
      } else {
        q.push(arr2[r++]);
      }
    }
    // if(total % 2==0) {
    //     int l = q.top(),q.pop();
    //     return (l+q.top()) /2;
    // }
    return q.top();
  }
};

#ifdef debug

int main(void) {

  Solution k;
  vector<int> a{1,9,19};
  vector<int> b{2,5,10};
  //   1 2 3  (3 4) 4 5 6
  println(k.findMedianinTwoSortedAray(a, b));
}

#endif