JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • 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;
    }
}