寻找两个正序数组的中位数

题目信息

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 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

解题思路

1. 暴力破解：合并两个数组后定位中位数
   1. 冒泡/选择/插入排序：时间复杂度O((m+n)^2)，空间复杂度O(1)
   2. 快排序：时间复杂度O((m+n)log(m+n))，空间复杂度O(m+n)
   3. 归并排序：时间复杂度O(m+n)，空间复杂度O(m+n)
2. 无效操作分析：中位数的计算与前后 (m + n - 2) / 2 个数无关
3. 优化方法：分治算法 + 求第 k 小数的特殊情况 + 对中位数概念的理解
4. 考虑边界：数组为空，数组为奇数还是偶数
5. 编码实现

代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 其中一个数组为空的情况
        if (nums1 == null || nums1.length == 0) {
            return findMedianSortedArrays(nums2);
        }
        if (nums2 == null || nums2.length == 0) {
            return findMedianSortedArrays(nums1);
        }
        // 不为空，分析两个数组
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            // 保证 m <= n
            return findMedianSortedArrays(nums2, nums1);
        }

        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            // 每次循环i都减半
            int i = (iMin + iMax) / 2;
            // 由 i + j = m - i + n - j + 1
            // 得出：2(i + j) = m + n + 1，即：j = (m + n + 1) / 2 - i
            int j = (m + n + 1) / 2 - i;
            // 最终需要保证nums2[j-1] < nums1[i]，并且nums1[i-1] > nums2[j]
            // 才能满足 max(nums1[i-1], nums[j-1]) <= min(nums[i], nums[j])
            // 才能得出结论：
            // 1. 奇数情况：中位数 = 左半部分最大值 = max(nums1[i-1], nums[j-1])
            // 2. 偶数情况：中位数 = 左半部分最大值 + 右半部分最小值 / 2 = max(nums1[i-1], nums[j-1]) + min(nums[i], nums[j]) / 2
            if (j != 0 && i != m && nums2[j-1] > nums1[i]){
                // i 需要增大
                iMin = i + 1; 
            } else if (i != 0 && j != n && nums1[i-1] > nums2[j]) { 
                // i 需要减小
                iMax = i - 1; 
            } else { 
                // 达到要求，并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) { 
                    maxLeft = nums2[j-1];
                } else if (j == 0) {
                    maxLeft = nums1[i-1];
                } else {
                    maxLeft = Math.max(nums1[i-1], nums2[j-1]); 
                }

                if ((m + n) % 2 == 1) {
                    // 奇数的话不需要考虑右半部分
                    return maxLeft; 
                } 

                //如果是偶数的话计算返回结果
                int minRight = 0;
                if (i == m) { 
                    minRight = nums2[j]; 
                } else if (j == n) { 
                    minRight = nums1[i]; 
                } else { 
                    minRight = Math.min(nums2[j], nums1[i]); 
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }

    private double findMedianSortedArrays(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        int mid = length / 2;
        if (length % 2 == 0) {
            return (nums[mid - 1] + nums[mid]) / 2.0;
        } 
        return nums[mid];
    }
}

核心详解：

题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。