寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数

你可以假设 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 len = nums1.length + nums2.length;
    int[] temp = new int[len];
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            temp[k++] = nums1[i++];
        } else {
            temp[k++] = nums2[j++];
        }
    }
    while (i < nums1.length) {
        temp[k++] = nums1[i++];
    }
    while (j < nums2.length) {
        temp[k++] = nums2[j++];
    }
    if (len % 2 == 0) {
        return (temp[len / 2] + temp[len / 2 - 1]) / 2.0;
    } else {
        return temp[len / 2];
    }
}

方法二：找中位数位置
为统一处理奇数和偶数情况，用left和right两个变量保存当前循环的值，每次用left替换right，表示上一个位置的值

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len = nums1.length + nums2.length;
    int i = 0, j = 0;
    int left = 0, right = 0;
    while (i + j <= len / 2) {
        left = right;
        if (i < nums1.length && (j >= nums2.length || nums1[i] < nums2[j])) {
            right = nums1[i];
            i++;
        } else {
            right = nums2[j];
            j++;
        }
    }
    if (len % 2 == 0) {
        return (left + right) / 2.0;
    } else {
        return right;
    } 
}

方法三：求两个数组中第k小的数

求两个数组中第k小的数：

由于4 < 12 ，抛弃掉A组的前4个元素，指针向后移动

总之就是每轮抛弃掉小于第k小元素的前k/2个

对抛弃掉的元素一定不是第k小的证明：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len = nums1.length + nums2.length;
    if (len % 2 == 0) {
        return (findKNums(nums1, nums2, len / 2) + findKNums(nums1, nums2, len / 2 + 1)) / 2.0;
    } else {
        return findKNums(nums1, nums2, len / 2 + 1);
    }
}

public int findKNums(int[] nums1, int[] nums2, int k) {
    int i = 0, j = 0;
    while (true) {
        if (i >= nums1.length) { //一个数组所有元素都删完了，第k小的数一定在另一个数组中
            return nums2[j + k - 1];
        }
        if (j >= nums2.length) {
            return nums1[i + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        int half = k / 2;
        int index1 = i + half - 1 >= nums1.length ? nums1.length - 1 : i + half - 1; //考虑数组剩余元素不够half个，最多只能取到末尾
        int index2 = j + half - 1 >= nums2.length ? nums2.length - 1 : j + half - 1;
        if (nums1[index1] < nums2[index2]) {
            k -= index1 - i + 1;
            i = index1 + 1;
        } else {
            k -= index2 - j + 1;
            j = index2 + 1;
        }
    }
}

时间复杂度：O(log(m+n))

方法四：划分数组

中位数将数组划分为两部分，不妨将中位数划分到左部分

如果是偶数，则为分割线左边最大的元素与右边最小元素的平均值
如果是奇数，则为分割线左边最大的元素

假设数组1长度为m，数组2长度为n
如果是偶数，划分在左边的元素个数(m+n)/2，由于除是向下取整，所以可以统一(m+n+1)/2
如果是奇数，划分在左边的元素个数(m+n+1)/2

左边的所有元素小于等于右边的所有元素：

第一个数组左边最后一个元素小于等于第二个数组右边第一个元素
- 不满足条件说明第一个数组的边界线应该向左移
第二个数组左边最后一个元素小于等于第一个数组右边第一个元素
- 不满足条件说明第一个数组的边界线应该向右移

特殊情况：

分割线的定义：分割线在数组的下标i=分割线左边的元素个数

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        int[] temp = nums1;
        nums1 = nums2;
        nums2 = temp;
    }
    int len = nums1.length + nums2.length;
    int totalLeft = (len + 1) / 2;
    int left = 0;
    int right = nums1.length;
    while (left < right) {
        int i = (left + right + 1) / 2; //加1是为了防止只有一个元素时left = i进入死循环
        int j = totalLeft - i;
        if (nums1[i - 1] > nums2[j]) {
            right = i - 1;
        } else {
            left = i;
        }
    }
    int i = left;
    int j = totalLeft - i;
    int num1Left = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
    int num1Right = i == nums1.length ? Integer.MAX_VALUE : nums1[i];
    int num2Left = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
    int num2Right = j == nums2.length ? Integer.MAX_VALUE : nums2[j];
    if (len % 2 == 0) {
        return (Math.max(num1Left, num2Left) + Math.min(num1Right, num2Right)) / 2.0;
    } else {
        return Math.max(num1Left, num2Left);
    }
}

时间复杂度：O(logmin(m,n)))