JAVA练习341- 寻找两个正序数组的中位数

题目概览

给定两个大小分别为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
• -10^6 <= nums1[i], nums2[i] <= 10^6

来源：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

解题分析

方法：二分查找

如果不考虑O(log (m+n))，正常遍历的做法应该是定义双指针 i1 和 i2 分别指向两个数组的头，令中位数的位置为 k，遍历比较 num1[i1] 和 nums2[i2]，最小的数指针 + 1，直到比较了 k 次，这样就拿到了中位数。

有了上面的思路，优化点在于指针是否可以加大于1的数来减少循环。由于得到中位数后，两个数组中至少有一个数组会移动至少 k / 2 的指针，因此我们可以通过比较 k / 2 处两个数组值的大小，小的数组直接移动 k / 2 来减少循环，移动完成后将 k 赋值为 k / 2 继续遍历直到得到中位数。

还要考虑一些边界情况：

1. 当移动后的指针大于等于数组的长度，指针调整为最后一个索引
2. 当一个数组遍历完成后，如果还有 k，另一个数组直接 +k 得到中位数
3. 当 m + n 为偶数时，需要再获取 k + 1 的中位数，两个中位数取和除以2

我们可以通过递归来实现。

时间复杂度：O(log (m+n))
空间复杂度：O(log (m+n))

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int k = (m + n + 1) / 2; double result = findMedianSortedArrays(nums1, nums2, 0, m - 1, 0, n - 1, k); if ((m + n) % 2 == 1) { return result; } return (result + findMedianSortedArrays(nums1, nums2, 0, m - 1, 0, n - 1, k + 1)) / 2.0; } public double findMedianSortedArrays(int[] nums1, int[] nums2, int i1, int j1, int i2, int j2, int k) { int n1 = j1 - i1 + 1; int n2 = j2 - i2 + 1; if (n1 == 0) { return nums2[i2 + k - 1]; } if (n2 == 0) { return nums1[i1 + k - 1]; } if (k == 1) { return Math.min(nums1[i1], nums2[i2]); } int i = Math.min(i1 + k / 2 - 1, nums1.length - 1); int j = Math.min(i2 + k / 2 - 1, nums2.length - 1); if (nums1[i] > nums2[j]) { return findMedianSortedArrays(nums1, nums2, i1, j1, j + 1, j2, k - (j - i2 + 1)); } return findMedianSortedArrays(nums1, nums2, i + 1, j1, i2, j2, k - (i - i1 + 1)); } }