关于leetcode:leetcode-4-Median-of-Two-Sorted-Arrays-寻找两个正序数组的中位数困难

27次阅读

共计 1345 个字符，预计需要花费 4 分钟才能阅读完成。

标签: 查找

https://leetcode.cn/problems/median-of-two-sorted-arrays

给定两个大小别离为 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

号称 leetcode 守门员的题。中位数能够来自于同一个数组，也能够来自于两个数组，能够是一个数，也能够是两个数。
实现思路（参考花花酱的解说）
分类：

思路：假如 n1,n2 是两个数组的元素，那么 k =(n1+n2+1)/ 2 就示意左中位数或中位数的索引，假如从 nums1 中取 m1 个元素，从 nums2 中取 m2 个元素，那么 m1+m2 = k。咱们要求的中位数就是从 max(nums[m1-1], nums[m2-1]) 和 min(nums[m1], nums[m2])。

public class Solution2 {public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        // 对长度小的数组做二分搜寻
        if (n1 > n2) {return findMedianSortedArrays(nums2, nums1);
        }

        // 偶数状况：nums1=>[1, 2, 3] nums2=>[3, 4, 5]  中位数 2 3
        // 奇数状况：nums1=>[1, 2, 3] nums2=>[2, 3, 4, 5] 中位数 3
        // nums1=>[-1, 1, 3, 5, 7, 9] nums2=>[2, 4, 6, 8, 10, 12, 14, 16]
        int l = 0;
        int r = n1;
        // 偶数状况：左中位数 奇数状况：中位数
        int k = (n1 + n2 + 1) / 2;
        while (l < r) {int m1 = l + (r - l) / 2;
            int m2 = k - m1;
            if (nums1[m1] < nums2[m2-1]) {l = m1 + 1;} else {r = m1;}
        }
        int m1 = l;
        int m2 = k - l;

        int c1 = Math.max(m1 < 1 ? Integer.MIN_VALUE : nums1[m1-1], m2 < 1 ? Integer.MIN_VALUE : nums2[m2-1]);
        // 奇数状况
        if ((n1 + n2) % 2 == 1) {return c1;}

        int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) * 0.5;
    }
}