leetCode刷题 4.寻找两个正序数组的中位数

1. 思路

2. 解题方法

3. 复杂度

4. Code

题目：

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

为了满足 O(log (m+n)) 的时间复杂度，我们可以尝试使用二分查找的思想来解决这个问题。我们的目标是找到两个有序数组合并后的中位数，也就是合并数组中的第 (m+n)/2 小的数。

2. 解题方法

我们可以对两个数组进行二分查找，每次排除一半的数据。首先，我们设定一个在合并数组中的位置 k，然后在两个数组中分别找到第 k/2 小的数，并比较它们的大小。如果数组1的第 k/2 小的数小于数组2的第 k/2 小的数，那么说明合并数组中的第 k 小的数一定不会在数组1的前 k/2 个数中，因此我们可以将数组1的前 k/2 个数排除，继续在剩余的数组中寻找第 k - k/2 小的数。以此类推，直到找到第 (m+n)/2 小的数。

如果合并数组的长度为偶数，则中位数为第 (m+n)/2 和 (m+n)/2 + 1 小的数的平均值。

定义一个辅助函数 findKth，该函数用于在两个有序数组中找到第 k 小的数。
在 findKth 函数中，比较两个数组的第 k/2 个数的大小，将较小的那个数的前 k/2 个数舍弃，并递归查找第 k - k/2 小的数。
如果某个数组已经全部被舍弃，则返回另一个数组的第 k 小的数。
在 findMedianSortedArrays 函数中，根据合并数组的长度奇偶性，调用 findKth 函数找到中位数。
返回中位数。

3. 复杂度

时间复杂度：O(log(min(m, n)))，其中 m 和 n 分别为两个数组的长度。每次二分查找的过程中，我们将问题的规模减半，因此时间复杂度为对数级别。
空间复杂度：O(1)。

4. Code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int totalLength = m + n;
        
        // 如果合并数组长度为奇数，则直接返回第 (m+n)/2 + 1 小的数
        if (totalLength % 2 == 1) {
            return findKth(nums1, nums2, totalLength / 2 + 1);
        } else { // 如果合并数组长度为偶数，则返回第 (m+n)/2 和 (m+n)/2 + 1 小的数的平均值
            return (findKth(nums1, nums2, totalLength / 2) + findKth(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
    
    // 辅助函数，用于在两个有序数组中找到第 k 小的数
    private double findKth(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int index1 = 0, index2 = 0;
        
        while (true) {
            // 处理其中一个数组已经全部被舍弃的情况
            if (index1 == len1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == len2) {
                return nums1[index1 + k - 1];
            }
            // 处理 k=1 的情况
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // 在两个数组中找第 k/2 小的数
            int newIndex1 = Math.min(index1 + k / 2 - 1, len1 - 1);
            int newIndex2 = Math.min(index2 + k / 2 - 1, len2 - 1);
            if (nums1[newIndex1] <= nums2[newIndex2]) {
                // 舍弃 nums1 中的前 k/2 个数
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            } else {
                // 舍弃 nums2 中的前 k/2 个数
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }
}

这段代码利用二分查找的思想，实现了在两个有序数组中找到第 k 小的数，并根据合并数组的长度奇偶性找到中位数，同时满足了 O(log (m+n)) 的时间复杂度要求。

5.小插曲：

有兴趣的可以计算一下下面代码的时间复杂度，把你的答案打在评论区吧！！！

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] merged = new int[m + n];
        
        int i = 0, j = 0, k = 0;
        // 使用归并排序合并两个正序数组
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        while (i < m) {
            merged[k++] = nums1[i++];
        }
        while (j < n) {
            merged[k++] = nums2[j++];
        }
        
        // 判断合并后数组的长度奇偶性，找到中位数
        if ((m + n) % 2 == 0) {
            int mid1 = merged[(m + n) / 2 - 1];
            int mid2 = merged[(m + n) / 2];
            return (double)(mid1 + mid2) / 2;
        } else {
            return (double)merged[(m + n) / 2];
        }
    }
}

欢迎大家后台联系讨论。