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

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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

二分法

分割两个数组，找到合适的下标 i 作为分割点，满足以下两个条件

第一个条件

使得分割线左边的元素个数大于等于分割线右边的元素个数

(m + n + 1) / 2就是左边分割线左边元素的个数

如果 i 指向nums1某个位置

j 指向的位置就是 (m + n + 1) / 2 - i

第二个条件

分割线左边所有元素的值都要小于右边的值

满足条件后，最终答案为

若m + n为奇数

res = min(nums1[i-1], nums2[j-1])

若m + n为偶数

res = max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums[j]) / 2

使用二分法不断调整 i 的位置

我们只需要使用二分法不断调整 i 的位置，使其满足以上两个条件即可

交叉比较对两个元素进行比较

nums2[j-1] > nums1[i] ， i 右移

下一轮搜索的区间为[i, right]

nums1[i-1] > nums2[j] , i 左移

下一轮搜索的区间为[left，i]

终止循环时，再讨论四种特殊情况

四种特殊情况

i = 0

i = m

j = 0

j = n

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //保证nums1长度比nums2长度小
        if(nums1.length > nums2.length){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        //m <= n
        int m = nums1.length;
        int n = nums2.length;

        //分割线左边满足元素的个数
        int totalLeft = (m + n + 1) / 2;        
        int left = 0;
        int right = m;
        //最终 left == right, 就是 i 的最终分割点
        while(left < right){
            int i = left + (right - left) / 2;
            int j = totalLeft - i;
            //交叉不满足条件
            if(nums2[j-1] > nums1[i]){ //i在右区间
                //下一轮搜索区间为[i+1,right]
                left = i + 1;
            }else{ //nums1[i-1] > nums1[j] //i在左区间  
                //下一轮搜索区间为[left, i]
                right = i;
            }
        }
        int i = left;
        int j = totalLeft - i;
        //四种i，j在边界的情况
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i-1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j-1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if((m + n) % 2 == 1){
            return Math.max(nums1LeftMax, nums2LeftMax);
        }else{
            return  (double) ((Math.max(nums1LeftMax,nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
        }
        
    }
}

时间复杂度：$O(log⁡ Math.min⁡(m,n))$

空间复杂度：$O(1)$

暴力解法

将两个有序数组归并为一个有序数组

再查找其中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] newNums = merge(nums1, nums2);
        int len = newNums.length;
        System.out.println(Arrays.toString(newNums));
        if(len % 2 == 1){
            return newNums[len/2];
        }else{
            return (newNums[len/2] + newNums[len/2-1]) / 2.0;
        }
    }

    public int[] merge(int[] nums1, int[] nums2){
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] newNums = new int[len1 + len2];
        int i = 0, j =0, k =0;
        while(i < len1 && j < len2){
            if(nums1[i] <= nums2[j]){
                newNums[k++] = nums1[i++];
            }else{
                newNums[k++] = nums2[j++];
            }
        }
        while(i < len1){
            newNums[k++] = nums1[i++];
        }
        while(j < len2){
            newNums[k++] = nums2[j++];
        }
        return newNums;
    }
}

时间复杂度：$O（m+n）$

空间复杂度：$O（m+n）$