4. Median of Two Sorted Arrays

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The 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^6 <= nums1[i], nums2[i] <= 10^6$

Code

index 0, 1, 2, 3, 4, 5, 6, 7
nums  1, 2, 3, 4, 5, 6, 7, 8
               k, k+1
如果是偶数个元素, 那么median是中间两个数相加/2, 也就是（第k个元素 + 第k+1个元素）/ 2

index 0, 1, 2, 3, 4, 5, 6
nums  1, 2, 3, 4, 5, 6, 7
            k, k+1
如果是奇数个元素, 那么中位数是中间的那个数, 也就是(n1+n2+1)/2 第4个元素, index是3

假设从nums1中取m1个元素, 从nums2中取m2个元素, 刚好构成了k个元素, 那么本题也就是求出从nums1中到底取多少个元素

合并之后的数组中, 第k个元素肯定是max(nums1中的第m1个元素，nums2中第m2个元素), 因为两个数组已经排序

合并之后的数组中, 第k+1个元素肯定是min(nums1中的第m1+1个元素, num2中第m2+1个元素), 因为两个数组已经排序

综上, 中位数的结果只和nums1中的第m1, m1+1个元素和nums2中的第m2, m2+1个元素有关

进行二分搜索的时候比较a[m1]和b[m2-1], 如果a[m1]<b[m2-1]说明nums1还应该继续取元素

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        // 减少操作次数
        if (len1 > len2) {
            // 确保N1是短的部分
            return findMedianSortedArrays(nums2, nums1);
        }

        // 开始从nums1中取元素
        int left = 0;
        int right = len1;

        while (left <= right) {
            // 从nums1和nums2中分别取m1和m2个元素组成k个元素
            int m1 = left + (right - left) / 2;
            int m2 = (len1 + len2) / 2 - m1;

            // k -> max(L1, L2), (k + 1) -> min(R1, R2)
            // nums1没有取元素?
            // 此时左边的元素一定从nums2中取，因此要使得L1 = MIN_VALUE
            // 这样max(L1, L2)就会取到L2了
            // 这时所取得元素中num2的元素都要比nums1中的小
            // 因此在min(R1,R2)的时候，选中的也是R2
            double m1Left = (m1 == 0) ? Integer.MIN_VALUE : nums1[m1 - 1];
            // nums1取了所有的元素?
            double m1Right = (m1 == len1) ? Integer.MAX_VALUE : nums1[m1];

            // nums2没有取元素?
            double m2Left = (m2 == 0) ? Integer.MIN_VALUE : nums2[m2 - 1];
            // nums2取了所有的元素?
            double m2Right = (m2 == len2) ? Integer.MAX_VALUE : nums2[m2];

            // 左边取多了
            if (m1Left > m2Right) {
                right = m1 - 1;
            }else if (m2Left > m1Right) {
                // 左边取少了
                left = m1 + 1;
            } else {
                // 此时是符合要求的排列情况
                if ((len1 + len2) % 2 == 0){
                    double medLeft = Math.max(m1Left, m2Left);
                    double medRight = Math.min(m1Right, m2Right);
                    return (medLeft + medRight) / 2.0;
                } else {
                    return Math.min(m1Right, m2Right);
                }
            }
        }

        return -1;
    }
}

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        len1 = len(nums1)
        len2 = len(nums2)
        if len1 > len2:
            return self.findMedianSortedArrays(nums2, nums1)
        left = 0
        right = len1
        while left <= right:
            # use m1 elements in nums1
            m1 = left + (right - left) // 2
            m2 = (len1 + len2) // 2 - m1
            m1_left = float("-inf") if m1 == 0 else nums1[m1 - 1]
            m1_right = float("inf") if m1 == len1 else nums1[m1]
            m2_left = float("-inf") if m2 == 0 else nums2[m2 - 1]
            m2_right = float("inf") if m2 == len2 else nums2[m2]
            if m1_left > m2_right:
                right = m1 - 1
            elif m2_left > m1_right:
                left = m1 + 1
            else:
                if (len1 + len2) % 2 == 0:
                    med_left = max(m1_left, m2_left)
                    med_right = min(m1_right, m2_right)
                    return (med_left + med_right) / 2
                else:
                    return min(m1_right, m2_right)
        return -1