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

题目概览给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log (mn))。示例 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 mnums2.length n0 m 10000 n 10001 m n 2000-10^6 nums1[i], nums2[i] 10^6来源4. 寻找两个正序数组的中位数 - 力扣LeetCode解题分析方法二分查找如果不考虑O(log (mn))正常遍历的做法应该是定义双指针 i1 和 i2 分别指向两个数组的头令中位数的位置为 k遍历比较 num1[i1] 和 nums2[i2]最小的数指针 1直到比较了 k 次这样就拿到了中位数。有了上面的思路优化点在于指针是否可以加大于1的数来减少循环。由于得到中位数后两个数组中至少有一个数组会移动至少 k / 2 的指针因此我们可以通过比较 k / 2 处两个数组值的大小小的数组直接移动 k / 2 来减少循环移动完成后将 k 赋值为 k / 2 继续遍历直到得到中位数。还要考虑一些边界情况当移动后的指针大于等于数组的长度指针调整为最后一个索引当一个数组遍历完成后如果还有 k另一个数组直接 k 得到中位数当 m n 为偶数时需要再获取 k 1 的中位数两个中位数取和除以2我们可以通过递归来实现。时间复杂度O(log (mn))空间复杂度O(log (mn))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)); } }