DX's Digital Garden

6._寻找两个数组中位数

8 min read

  • 3.18
  • 3.17
    • 做了一小时
    • 右边一定比左边数组大，不然右边数组中指针会出现负数
    • (m+n+1)/2 是逻辑左半边，作用是定位右边数组的中指针
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length>nums2.length) return findMedianSortedArrays(nums2,nums1);
 
        int m = nums1.length;
        int n = nums2.length;
 
        int totalLeft = (m+n+1)/2;
        int left = 0;
        int right= m;
 
        while(left<=right){
            int midLeft = (left+right)/2;
            int midRight = totalLeft-midLeft;
 
            int midLeftL = (midLeft==0)?Integer.MIN_VALUE:nums1[midLeft-1];
            int midLeftR = (midLeft==m)?Integer.MAX_VALUE:nums1[midLeft];
            int midRightL = (midRight==0)?Integer.MIN_VALUE:nums2[midRight-1];
            int midRightR = (midRight==n)?Integer.MAX_VALUE:nums2[midRight];
 
 
            if(midLeftL<=midRightR&&midRightL<=midLeftR){
                if((m+n)%2==1){
                    return Math.max(midLeftL,midRightL);
                }else{
                    return (Math.max(midLeftL,midRightL)+Math.min(midLeftR,midRightR))/2.0;
                }
            }else if(midLeftL>midRightR){
                right = midLeft-1;
            }else{
                left = midLeft+1;
            }
        }
        return 0.0;
    }
}
  • 2.14
    • 计算总长度
    • while 循环里算出左右数组的中点
    • 算出两个中点左右数，看情况移动左中点位置
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length>nums2.length){
            return findMedianSortedArrays(nums2,nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
 
        int left = 0;
        int right = m;
 
        int totalLeft = (m+n+1)/2;
        while(left<=right){
            int leftMid = (left+right)/2;
            int rightMid = totalLeft-leftMid;
 
            int nums1LeftMid =  (leftMid==0)?Integer.MIN_VALUE:nums1[leftMid-1];
            int nums1RightMid = (leftMid==m)?Integer.MAX_VALUE:nums1[leftMid];
            int nums2LeftMid = (rightMid==0)?Integer.MIN_VALUE:nums2[rightMid-1];
            int nums2RightMid = (rightMid==n)?Integer.MAX_VALUE:nums2[rightMid];
 
            if(nums1LeftMid<=nums2RightMid&&nums2LeftMid<=nums1RightMid){
                if((m+n)%2==1){
                    return Math.max(nums1LeftMid,nums2LeftMid);
                }else{
                    return (Math.max(nums1LeftMid,nums2LeftMid)+Math.min(nums1RightMid,nums2RightMid))/2.0;
                }
            }else if(nums1LeftMid>nums2RightMid){
                right = leftMid-1;
            }else{
                left = leftMid+1;
            }
        }
        return 0.0;
    }
}
  • 1.31
    • 以数组 1 的长度为左右指针（数组 1 必须是短的那一方）
    • 分别找出数组 1 和 2 的中间位置的两边的数
    • 看是否满足”交叉小于等于“关系，根据大小，移动数组 1 的分割点
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 1. 确保 nums1 是较短的那个数组，这样二分效率更高，且避免 j 计算越界
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
 
        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;
        
        // 左半部分的总个数（如果是奇数，左边多一个）
        int totalLeft = (m + n + 1) / 2;
 
        while (left <= right) {
            // i 是 nums1 的分割点
            int i = (left + right) / 2;
            // j 是 nums2 的分割点
            int j = totalLeft - i;
 
            // 处理边界值：如果分割线在最左边，左边就是负无穷；在最右边，右边就是正无穷
            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 (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
                // 【完美切分！】
                
                // 如果总长度是奇数，中位数就是左半边的最大值
                if ((m + n) % 2 == 1) {
                    return Math.max(nums1LeftMax, nums2LeftMax);
                } 
                // 如果总长度是偶数，中位数是 (左半边最大 + 右半边最小) / 2
                else {
                    return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
                }
            } 
            else if (nums1LeftMax > nums2RightMin) {
                // nums1 左边太大了，说明切分线 i 划得太靠右，需要左移
                right = i - 1;
            } 
            else {
                // nums2 左边太大了（意味着 nums1 右边太小），说明 i 划得太靠左，需要右移
                left = i + 1;
            }
        }
        return 0.0;
    }
}

1. 我们的终极目标是什么？

假设我们用一把刀，把 nums1 切成左右两半（切口位置是 i），把 nums2 也切成左右两半（切口位置是 j）。

为了找到中位数，这把刀必须满足一个交叉小于等于的终极条件：

  1. nums1 左边最大的数 (nums1LeftMax) $\le$ nums2 右边最小的数 (nums2RightMin)

  2. nums2 左边最大的数 (nums2LeftMax) $\le$ nums1 右边最小的数 (nums1RightMin)

如果满足了，说明我们切得非常完美，左半边的所有数都小于右半边。

2. 为什么会出现 i == 0 或 i == m？

正常情况下，刀切在数组中间，左右都有数字。比如 [1, 3 | 5, 7]，左边最大是 3，右边最小是 5。

但是，如果数组长度差异很大，或者数值差异很大，刀可能会切在最边缘！

场景 A：刀切在了最左边 (i == 0)

假设 nums1 = [8, 9]，nums2 = [1, 2, 3, 4]。

很明显，中位数肯定在 nums2 里。当我们切分时，nums1 里的数字太大，一个都不应该分到左半边。

也就是刀切在了 nums1 的最开头： | 8, 9。

  • 问题来了：此时 nums1 的左边是空的！程序如果要强行去取 nums1[i - 1]（也就是 nums1[-1]），直接就数组下标越界报错了。

  • 解决思路：既然左边是空的，而我们的条件是“左边的数必须 $\le$ 右边的数”。为了让这个条件绝对成立且不影响判断，我们给这个“空”赋予一个极小值（负无穷）。

  • 代码翻译：int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];

    (只要切在最左边，左边的最大值就是 $-\infty$，这样 $-\infty$ 无论跟谁比都肯定 $\le$ 对方，完美通关！)

场景 B：刀切在了最右边 (i == m)

假设 nums1 = [1, 2]，nums2 = [8, 9, 10, 11]。

同理，nums1 里的数字太小，全部都应该分到左半边。

也就是刀切在了 nums1 的最末尾：1, 2 |。

  • 问题来了：此时 nums1 的右边是空的！程序如果要强行去取 nums1[i]（也就是 nums1[2]），也会越界报错。

  • 解决思路：右边是空的，我们的条件是“左边的数必须 $\le$ 右边的数”。为了让任何左边的数都能 $\le$ 这个右边的“空”，我们给它赋予一个极大值（正无穷）。

  • 代码翻译：int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];

    (只要切在最右边，右边的最小值就是 $+\infty$，这样无论左边是谁，都肯定 $\le +\infty$，再次完美通关！)

3. 一句话总结

这段代码就是为了防止数组越界发明的**“障眼法”**：

  • 当左边没数时，塞一个 负无穷，假装它存在，且保证它比任何数都小。

  • 当右边没数时，塞一个 正无穷，假装它存在，且保证它比任何数都大。

Graph View