给定两个大小分别为
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 == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
思路：
- 方法1 先将两个数组有序合并至新数组中，然后根据奇偶情况返回中位数
- 方法2 先找到中位数可能的下标值 left 和 right，然后遍历数组得到 nums[left], nums[right]，再根据奇偶情况返回中位数
- 方法3 二分法，题目要求 算法的时间复杂度应该为
O(log (m+n))，此方法待研究 ...
时间复杂度：
- 方法1 O(m+n)
- 方法2 遍历
len/2 + 1次，len=m+n，所以时间复杂度依旧是 O(m+n) - 方法1
O(log (m+n))
空间复杂度：
- 方法1 O(m+n)
- 方法2 O(1)
- 方法3 O(1)
// 方法1 先将两个数组有序合并至新数组中，然后根据奇偶情况返回中位数// 空间复杂度：O(m+n)funcfindMedianSortedArrays(nums1 []int, nums2 []int) float64 { i, j, length1, length2 :=0, 0, len(nums1), len(nums2) newNums :=make([]int, 0, length1+length2) fori, j=0, 0; i<length1&&j<length2; { ifnums1[i] <nums2[j] { newNums=append(newNums, nums1[i]) i++ } else { newNums=append(newNums, nums2[j]) j++ } } ifi<length1 { newNums=append(newNums, nums1[i:]...) } ifj<length2 { newNums=append(newNums, nums2[j:]...) } // 1 2 3(2) 4 5if (length1+length2) %2!=0 { returnfloat64(newNums[(length1+length2-1)/2]) } // 1 2 3(2) 4(3) 5 6returnfloat64(newNums[(length1+length2)/2] +newNums[(length1+length2)/2-1]) /float64(2) } // 方法2 先找到中位数可能的下标值left和right，然后遍历数组得到nums[left],nums[right]，再根据奇偶情况返回中位数// 空间复杂度：O(1) 具体思路如下：// 1.先根据nums1和nums2的数组长度，判断 奇数/偶数 情况，得到应返回的中位数下标left,right// 奇数：left = right// 偶数：left = right - 1// 2.分别遍历nums1和nums2数组，每次找出nums1[i]和nums2[j]中的较小者。然后i，j和k（用来标记当前k是否正好是中位数的left/right下标）分别右移一位// 如果k正好是中位数的left/right下标，找到其对应值，根据奇偶情况返回不同的res值即可// 若是奇数情况，在找到了一个中位数下标后可直接返回；// 若是偶数则当 k == right，说明已经找到了两个中位数，可提前结束循环并处理res值返回funcfindMedianSortedArrays(nums1 []int, nums2 []int) float64 { // 先找到奇数或偶数情况下，分别对应的中位数下标l1, l2, left, right, isOdd :=len(nums1), len(nums2), 0, 0, false// 偶数：1 2(1); 3(2) 4【左1右1】 // 1; 2(1) 3(2) 4【右2】 // 1 2(1) 3(2); 4【左2】if (l1+l2)%2==0 { right= (l1+l2) /2left=right-1isOdd=false// 奇数：1 2 3(2); 4 5 ... } else { left= (l1+l2) /2right=left// left和right一样isOdd=true } i, j, k, tmp :=0, 0, 0, 0varresfloat64fori<l1||j<l2 { ifi<l1&&j<l2&&nums1[i] <=nums2[j] { tmp=nums1[i] i++ } elseifi<l1&&j<l2&&nums1[i] >=nums2[j] { tmp=nums2[j] j++ } elseifi<l1 { tmp=nums1[i] i++ } elseifj<l2 { tmp=nums2[j] j++ } ifk==left||k==right { res+=float64(tmp) ifisOdd||k==right { // 奇数直接返回结果，偶数则继续找第二个中位数break// return res } } k++ } ifisOdd { returnres } returnres/2} // 上边的两种思路，时间复杂度都达不到题目的要求 O(log(m+n)。看到 log，很明显，我们只有用到二分方法才能达到。二分法待研究。。// 该方法为上述方法2优化之前的代码，较为繁琐// // func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {// // 先找到奇数或偶数情况下，分别对应的中位数下标// l1, l2, left, right, isOdd := len(nums1), len(nums2), 0, 0, false// // 偶数：1 2(1); 3(2) 4【左1右1】 // 1; 2(1) 3(2) 4【右2】 // 1 2(1) 3(2); 4【左2】// if (l1+l2)%2 == 0 {// right = (l1 + l2) / 2// left = right - 1// isOdd = false// // 奇数：1 2 3(2); 4 5 ...// } else {// left = (l1 + l2) / 2// right = left // left和right一样// isOdd = true// }// // fmt.Printf("%v, %v, %v \n", isOdd, left, right)// i, j, k, tmp := 0, 0, 0, 0// var res float64// for i < l1 && j < l2 {// if nums1[i] < nums2[j] {// tmp = nums1[i]// i++// } else {// tmp = nums2[j]// j++// }// if k == left || k == right {// res += float64(tmp)// if isOdd { // 奇数直接返回结果，偶数则继续找第二个中位数// return res// }// }// k++// }// // fmt.Printf("i=%v, j=%v, k=%v, l1=%v, l2=%v, left=%v, right=%v\n", i, j, k, l1, l2, left, right)// // 如果nums1或nums2其中一个数组遍历完了，且中位数还未找完，则继续遍历另一个数组// for i < l1 {// if k == left || k == right {// res += float64(nums1[i])// // 奇数直接返回结果。偶数时，k已经等于第二个中位数的下标了，说明中位数都已经找完了// if isOdd || k == right {// break// }// }// i++// k++// }// for j < l2 {// if k == left || k == right {// res += float64(nums2[j])// // 奇数则找到第一个中位数后直接返回，偶数则继续找第二个中位数// if isOdd || k == right { // 奇数 或 偶数时，k已经等于第二个中位数的下标了// break// }// }// j++// k++// }// if isOdd {// return res// }// return res / 2// }
