Leetcode4:寻找两个正数数组中的中位数

原题地址：. - 力扣（LeetCode）

题目描述：

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

做题步骤

1. 空数组检查：首先检查两个数组是否都为空，如果都为空，则返回0。

2. 合并数组：

   • 创建一个新数组 dummy，其长度为两个数组长度之和。
   • 将 nums1 数组的所有元素复制到 dummy 数组的前 nums1.length 个位置。
   • 将 nums2 数组的所有元素复制到 dummy 数组的后 nums2.length 个位置。

3. 检查数组长度：检查合并后的数组 dummy 的长度是否小于2，如果是，则直接返回 dummy 数组的第一个元素作为中位数。

4. 排序：

   • 对合并后的数组 dummy 进行排序。

5. 计算中位数：

   • 如果 dummy 数组的长度是偶数，则中位数是 dummy 数组中间两个数的平均值。
   • 如果 dummy 数组的长度是奇数，则中位数是 dummy 数组中间的数。

6. 返回结果：返回计算出的中位数。

代码行描述leet

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 检查两个数组是否都为空
        if(nums1==null && nums2==null){
            return 0;
        }

        // 合并数组
        int[] dummy = new int[nums1.length+nums2.length];
        for (int i = 0;i<nums1.length; i++){
            dummy[i] = nums1[i];
        }
        for(int i = 0;i<nums2.length;i++){
            dummy[nums1.length+i] = nums2[i];
        }

        // 如果合并后的数组长度小于2，直接返回第一个元素
        if(dummy.length < 2){
            return dummy[0];
        }

        // 对合并后的数组进行排序
        Arrays.sort(dummy);

        // 计算中位数
        // 如果数组长度是偶数，返回中间两个数的平均值
        if(dummy.length%2 == 0){
            return (dummy[dummy.length / 2] + dummy[dummy.length / 2 -1]) / 2.0;
        }
        // 如果数组长度是奇数，返回中间的数
        return dummy[dummy.length / 2];
    }
}

总结

• 算法思想：通过合并两个有序数组，然后对合并后的数组进行排序，最后根据数组长度的奇偶性来确定中位数。
• 时间复杂度：O((m+n)log(m+n))，其中 m 和 n 分别是两个数组的长度。这是因为合并后的数组排序操作的时间复杂度是 O((m+n)log(m+n))。
• 空间复杂度：O(m+n)，因为创建了一个长度为 m+n 的新数组来合并两个数组。
• 优化点：实际上，这个问题可以通过更高效的方法解决，即利用两个数组的有序性，使用二分查找法来找到中位数，这样可以将时间复杂度降低到 O(log(min(m,n)))。这种方法不需要合并数组和进行全数组排序，因此在处理大规模数据时更加高效。