题目
合并有序数组间接返回中位数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {var nums3 []int
var a,b int
// 合并数组
for a<len(nums1)&&b<len(nums2){if nums1[a]<nums2[b]{nums3=append(nums3,nums1[a])
a++
}else {nums3=append(nums3,nums2[b])
b++
}
}
if a==len(nums1){nums3=append(nums3,nums2[b:len(nums2)]...)
}else{nums3=append(nums3,nums1[a:len(nums1)]...)
}
// 取中位数
if len(nums3)%2==1{return float64(nums3[len(nums3)/2])
}else{return (float64(nums3[len(nums3)/2-1])+float64(nums3[len(nums3)/2]))/2
}
}复杂度
工夫 O（m+n）
空间 O（1）
合并数组应用了太多工夫，将其优化为 log
因为两个数组都为有序数组，在指标数字之前的数都必然小于它，这就容许咱们进行疾速的排除
定义 i，j 两个指针，每次排除 k / 2 个必然不是中位数的数，并将指针前移
直到非凡状况找到第 k 个数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {//find (m+n+1)/2 and (m+n+2)/2
m:=len(nums1)
n:=len(nums2)
res1:=getKthElement(nums1,nums2,(m+n+2)/2)
res2:=getKthElement(nums1,nums2,(m+n+1)/2)
return (float64(res1)+float64(res2))/2
}
func getKthElement(nums1 []int, nums2 []int, k int)int{
var index1,index2 int
for {
// 如果一个数组已被排查完，间接返回另一个数组的第 k 个元素
if index1 == len(nums1) {return nums2[index2 + k - 1]
}
if index2 == len(nums2) {return nums1[index1 + k - 1]
}
// 如果要找最小的元素，则只有两种可能性，间接比拟找到后果
if k == 1 {return min(nums1[index1], nums2[index2])
}
// 更新排除的数 k /2，实现比拟，排除小于 k 的数，k 值减小
half := k/2
newIndex1 := min(index1 + half, len(nums1)) - 1
newIndex2 := min(index2 + half, len(nums2)) - 1
pivot1, pivot2 := nums1[newIndex1], nums2[newIndex2]
if pivot1 <= pivot2 {k -= (newIndex1 - index1 + 1)
index1 = newIndex1 + 1
} else {k -= (newIndex2 - index2 + 1)
index2 = newIndex2 + 1
}
}
}
func min(x, y int) int {
if x < y {return x}
return y
}