【LeetCode】4、寻找两个正序数组的中位数
4、寻找两个正序数组的中位数
给定两个大小分别为 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
解题思路：
此题寻找两个正序数组的中位数，并不难，但限制了算法的时间复杂度为： O(log (m+n)) 。
看着这个时间复杂度，不知道有没有小伙伴想起什么。
是的，就是二分查找！我们可以理由二分查找的思想来解决此题。
但是有两种解题思路：
第一种是：使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。
第二种是：不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。
假设两个有序数组的长度分别为 mm 和 nn，上述两种思路的复杂度如何？
第一种思路的时间复杂度是 O(m+n)O(m+n)，空间复杂度是 O(m+n)O(m+n)。第二种思路虽然可以将空间复杂度降到 O(1)O(1)，但是时间复杂度仍是 O(m+n)O(m+n)。
如何把时间复杂度降低到 O(\log(m+n))O(log(m+n)) 呢？如果对时间复杂度的要求有 \loglog，通常都需要用到二分查找，这道题也可以通过二分查找实现。
模拟解题：
本文使用第二种，不合并数组：
根据中位数定义：如果某个有序数组长度是奇数，那么其中位数就是最中间那个，如果是偶数，那么就是最中间两个数字的平均值。
- 假设两个有序数组的长度分别为m和n，由于两个数组长度之和 m+n 的奇偶不确定，因此需要分情况来讨论
- 对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。
- 为了简化代码，不分情况讨论，我们使用一个小trick，我们分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2
个，然后求其平均值即可，这对奇偶数均适用 - 加入 m+n 为奇数的话，那么其实
(m+n+1) / 2 和 (m+n+2) / 2的值相等，相当于两个相同的数字相加再除以2，还是其本身。
参考代码：
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n = nums1.length; int m = nums2.length; int left = (n+m+1)/2; int right = (n+m+2)/2; return (findKth(nums1,0,nums2,0,left)+findKth(nums1,0,nums2,0,right))/2.0; } //i: nums1的起始位置 j: nums2的起始位置 int findKth(int[] nums1, int i, int[] nums2, int j, int k){ if( i >= nums1.length) return nums2[j + k - 1];//nums1为空数组 if( j >= nums2.length) return nums1[i + k - 1];//nums2为空数组 if(k == 1){ return Math.min(nums1[i], nums2[j]); } int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE; int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE; if(midVal1 < midVal2){ return findKth(nums1, i + k / 2, nums2, j , k - k / 2); }else{ return findKth(nums1, i, nums2, j + k / 2 , k - k / 2); } }}
欢迎喜欢算法的同学一起来探讨最优算法。