4. Median of Two Sorted Arrays (opens new window)

Description

Difficulty: Hard

Related Topics: Array (opens new window), Binary Search (opens new window), Divide and Conquer (opens new window)

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

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

Solution

Language: JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 当两个有序数组的长度之和为奇数的时候，中位数只有1个，将它返回；
 当两个有序数组的长度之和为偶数的时候，中位数有2个，返回合并、排序以后位于中间的两个数的平均数。
 
 方法一：暴力求解
 先合并两个有序数组
 然后排序找到中位数
 没有使用数组有序这一条件
 
 方法二：合并两个有序数组
 借鉴归并排序的关键步骤【合并两个有序数组】（参考【力扣88题】），将时间复杂度降到O(m+n)
 后面的部分和【暴力解法】一样
 事实上，也可以不用合并完，就能得到答案。
 
 方法三：二分查找
 中位数：在只有一个有序数组的时候，中位数把数组分割成两个部分。
 根据定义，分数组长度为奇数和偶数的讨论。
 
 数组长度为偶数时，中位数有两个，其中一个是左边数组的最大值，另一个是右边数组的最小值。
 数组长度为奇数时，中位数有1个，我们不妨把中位数分到左边数组。
 
 中位数：在有两个有序数组的时候，仍然可以把两个数组分割成两个部分。
 我们使用一条分割线把两个数组分别分割成两部分。
 1.红线左边和右边的元素个数相等，或者左边元素的个数比右边元素的个数多1个；
 2.红线左边的所有元素的数值<=红线右边的所有元素的数值；
 那么中位数就一定只与红线两侧的元素有关，确定这条红线的位置使用二分查找。
 
 分割线左边5个元素，分割线右边4个元素
 当两个数组的元素个数之和为奇数的时候，有l[size]=r[size]+1
 分割线左边元素的最大值就是数组的中位数
 
 分割线左边5个元素，分割线右边5个元素
 当两个数组的元素个数之和为偶数的时候，有l[size]=r[size]
 分割线左边的元素的最大值就是其中的一个中位数
 分割线右边的元素的最小值就是另外一个中位数
 
 又由于这两个数组都是有序的数组，分割线左边的这两个元素的较大值，就是分割线左边的所有元素的最大值，它是其中一个中位数；分割线右边的这两个元素的较小值，就是分割线右边的所有元素的最小值，它是另外一个中位数。
 
 假设数组1的长度为m，假设数组2的长度为n
 当m+n为偶数的时候，l[size]=(m+n)/2=(m+n+1)/2
 当m+n为奇数的时候，由于我们之前假设中位数被分到左边，l[size]=(m+n+1)/2;
 因此，可以把以上两种写法合并，l[size]=(m+n+1)/2
 得到这个结论的好处是，不用分奇数讨论，只需要确定其中一个数组的分割线位置，另一个数组的分割线位置可以通过公式计算出来。
 此时满足的中位数分割线的第1个条件。
 
 接下来我们看中位数要保持的第2个条件：红线左边的所有元素数值<=红线右边的所有元素数值。
 由于两个数组都是有序数组，在同一个数组内，分割线一定满足左边的所有元素小于右边的所有元素。
 在不同的数组之间，应该保证交叉小于等于关系成立。
 
 第一个数组在分割线左边的最大值要小于等于第二个数组在分割线右边的最小值，并且第二个数组在分割线左边的最大值也要小于等于第一个数组在分割线右边的最小值，这样的分割线才是我们需要的。
 那么，只要不符合交叉小于等于关系，我们就需要适当调整分割线的位置。
 
 分情况：
 
 中位数分割线右边的数太小
 调整方案：将中位数分割线在数组1的位置右移
 说明：第二个数组的分割线左边的最大值 大于 第一个数组在分割线右边的最小值
 
 中位数分割线左边的数太大
 调整方案：将中位数分割线在数组1的位置左移
 说明：第一个数组的分割线左边的最大值 大于 第二个数组的分割线右边的最小值
 
 m=2,n=9,左6右5               m=3,n=9,左6右6
 由于我们需要通过访问“中间数分割线”左右两边的元素，因此应该在较短的数组上确定“中间数分割线”的位置。
 
 当两个数组长度相等的时候
 
 定义分割线：
 分割线在第1个数组右边的第1个元素的下标i=分割线在第1个数组左边的元素个数
 分割线在第2个数组右边的第1个元素的下标j=分割线在第2个数组左边的元素个数
 
 totalLeft = i+j = (m+n+1)/2
 在nums1的区间[0, m]里查找恰当的分割线
 使得nums1[i-1] <= nums2[j] && nums2[j-1] <= num1[i]
 left = 0, right = m;
 i = left + (right-left+1)/2;
 j = totalLeft - i
 
 下一轮搜索的区间[left, i-1]
 下一轮搜索的区间[i, right]
 nums[i-1]>nums2[j] ? right = i-1 : left = i
 */
var findMedianSortedArrays = function(nums1, nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    
    const [m, n] = [nums1.length, nums2.length];
    let [left, right, min, max] = [0, m, -Infinity, Infinity];
    
    while (left <= right) {
        const i = (left + right) >>> 1;
        const j = ((m + n + 1) >> 1) - i;
        
        const L1 = !i ? min : nums1[i-1]
        const R1 = i === m ? max : nums1[i]
        const L2 = !j ? min : nums2[j-1]
        const R2 = j === n ? max : nums2[j]
        
        if(L1 <= R2 && L2 <= R1) {
            const leftMax = Math.max(L1, L2);
            return (m+n)%2 === 1 ? leftMax : (leftMax + Math.min(R1, R2)) / 2;
        }
        
        L1 > R2 ? (right = i - 1) : (left = i + 1)
    }
};