4.median-of-two-sorted-arrays

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

解法：
看到题目，第一反应直接使用归并排序中的并操作，找到中间的一个元素(或两个元素的平均值)并返回即可

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
    int i = 0, j = 0;
    int m = nums1.length;
    int n = nums2.length;
    int[] arr = new int[(m + n) / 2 + 1];
    int k = 0;
    while(i + j <= (m + n) / 2) {

        if(i > m - 1) {
            arr[k] = nums2[j];
            j++;
        } else if(j > n - 1) {
            arr[k] = nums1[i];
            i++;
        } else if(nums1[i] < nums2[j]) {
            arr[k] = nums1[i];
            i++;
        } else {
            arr[k] = nums2[j];
            j++;
        }
        k++;
    }
    if((m + n) % 2 == 0) {
        return (arr[(m + n) / 2 - 1] + arr[(m + n) / 2]) / 2.0;
    } else {
        return arr[(m + n) / 2];
    }
}

上述算法空间复杂度为O(n)（开辟了一个新的数组arr的存储空间），时间复杂度为O(n)（事实上是对两个数组元素个数和的一半进行了遍历），理论上来说应该算比较快的了。

但是根据题目的要求，算法的时间复杂度要为 O(log(m + n))，显然上述算法是不满足条件的，那么该如何才能使算法满足条件?看到这个O(log(m+n))，很容易想到二分法。因此猜测本题可以使用二分法来求解。

使用二分法的思想来求解本题
我们可以看到，本题的两个数组均为有序数组，因此，假如我们二分这两个数组，就可以得到四个部分:

设 
m = nums1.length, n = nums2.length;
i = m / 2, j = n /2;
则二分以后得到四个部分:
nums1[0...i-1]，nums1[i....m-1],
nums2[0...j-1]，nums2[j....n-1]

分析二分两个数组以后的结果，假如我们将这四部分归为两部分，nums1的前半部分和nums2的前半部分为一组，nums1的后半部分和nums2的后半部分为一组，即

nums1[0..i-1]与nums2[0...j-1]为一组
nums1[i...m-1]与nums2[j....n-1]为一组

这样我们就得到了元素个数相对均衡的两组，这也是我们的初始状态。
在这种状态下，我们考虑一种最为理想的情况:
max{nums1[i-1], nums2[j-1]} < min{nums1[i]， nums2[j]}
即我们分成的两组元素的第一组最大值都小于第二组的最小值，也就是说第一组所有元素都小于第二组所有元素，显然，在这种情况下，我们只需要考虑各组的边界值就可以很容易的求解中位数了。
比如说原始的两个数组元素个数均为偶数，这种情况下，我们分成的两组数据元素个数相同，中位数必然为(max{nums1[i-1], nums2[j-1]} + min{nums1[i], nums2[j]})/2。同样其它情况下只需要进行一下逻辑上的分析就可以得到答案。

现在我们需要做的就是得到这样一种理想的状态：将两个数组经过二分 (不是真正意义上的二分）划分成两部分，这两部分满足这样一种关系，即

  • 前一部分元素与后一部分元素个数相等或者相差1个元素（考虑整体元素个数为奇数和偶数）
     // 假设我们进行了如下划分
 // 将数组nums1划分为num1[0...i-1] 和 nums1[i....m - 1]，这种划分有m + 1种（i从0取值到m）
 // 将数组nums2划分为num2[0...j-1] 和 nums2[j....n - 1]， 这种划分有n + 1种（i从0取值到n）
 // 事实上要满足前一部分元素与后一部分元素个数相等或者相差1个元素，则只要i和j其中之一定了，另一个也会定下来
 // 即j = (m + n + 1) / 2 - i  (这里(m + n + 1) / 2是前一部分元素个数，在原始数组整体元素个数为奇数的情况下，中位数划分到第一部分)
  • 前一部分所有元素都小于后一部分的所有元素
     //nums1[0..i-1]与nums2[0...j-1]为一组
 //nums1[i...m-1]与nums2[j....n-1]为一组
 //只需要满足以下条件
 nums1[i - 1]  < nums2[j] && nums2[j - 1] < nums2[i] 
 //这是因为nums1[i - 1] < nums[i]， nums2[j - 1] < nums2[j]显然成立

未完待续