题目描述
给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
示例
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解题思路 - 二分查找法
我们可以使用二分查找法来解决这个问题。关键在于找到两个数组中第k小的数，其中k是两个数组长度之和的一半。如果两个数组的长度之和是奇数，那么中位数就是第k小的数；如果是偶数，那么中位数是第k小和第k+1小的数的平均值。
我们可以分别在两个数组中进行二分查找，每次比较两个数组中第k/2个元素的大小，然后根据比较结果排除掉一定不可能包含中位数的部分，从而缩小查找范围。
Go语言实现 - 二分查找法
下面是使用Go语言实现的代码：
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
totalLength := len(nums1) + len(nums2)
if totalLength%2 == 1 {
return float64(findKthElement(nums1, nums2, totalLength/2+1))
} else {
left := findKthElement(nums1, nums2, totalLength/2)
right := findKthElement(nums1, nums2, totalLength/2+1)
return float64(left+right) / 2.0
}
}
func findKthElement(nums1, nums2 []int, k int) int {
index1, index2 := 0, 0
for {
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])
}
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
}
算法分析
- 时间复杂度: O(log(min(m, n)))，因为我们每次都会排除掉一定比例的元素。
- 空间复杂度: O(1)，因为我们只需要常数级别的额外空间来存储索引和临时变量。
合并数组法
最直接的方法是将两个数组合并成一个有序数组，然后根据合并后数组的长度是奇数还是偶数，找到中位数。这种方法的时间复杂度是O(m+n)，因为合并两个数组需要遍历所有元素。
Go语言实现 - 合并数组法
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
merged := mergeSortedArrays(nums1, nums2)
n := len(merged)
if n%2 == 1 {
return float64(merged[n/2])
}
return float64(merged[n/2-1]+merged[n/2]) / 2.0
}
func mergeSortedArrays(nums1, nums2 []int) []int {
merged := make([]int, 0, len(nums1)+len(nums2))
i, j := 0, 0
for i < len(nums1) && j < len(nums2) {
if nums1[i] < nums2[j] {
merged = append(merged, nums1[i])
i++
} else {
merged = append(merged, nums2[j])
j++
}
}
for ; i < len(nums1); i++ {
merged = append(merged, nums1[i])
}
for ; j < len(nums2); j++ {
merged = append(merged, nums2[j])
}
return merged
}
算法分析
- 时间复杂度: O(m+n)，因为需要合并两个数组。
- 空间复杂度: O(m+n)，因为需要额外的空间来存储合并后的数组。
双指针法
另一种方法是使用双指针，分别遍历两个数组。这种方法不需要合并数组，而是通过指针来找到中位数。
Go语言实现 - 双指针法
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m, n := len(nums1), len(nums2)
left, right := (m+n+1)/2, (m+n+2)/2
return float64(findKth(nums1, 0, nums2, 0, left)+findKth(nums1, 0, nums2, 0, right)) / 2.0
}
func findKth(nums1 []int, i int, nums2 []int, j int, k int) int {
if i >= len(nums1) {
return nums2[j+k-1]
}
if j >= len(nums2) {
return nums1[i+k-1]
}
if k == 1 {
return min(nums1[i], nums2[j])
}
midVal1, midVal2 := math.MaxInt32, math.MaxInt32
if i+k/2-1 < len(nums1) {
midVal1 = nums1[i+k/2-1]
}
if j+k/2-1 < len(nums2) {
midVal2 = nums2[j+k/2-1]
}
if midVal1 < midVal2 {
return findKth(nums1, i+k/2, nums2, j, k-k/2)
}
return findKth(nums1, i, nums2, j+k/2, k-k/2)
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
算法分析
- 时间复杂度: O(m+n)，在最坏的情况下，每次递归都会排除掉一个元素。
- 空间复杂度: O(1)，因为不需要额外的空间来存储合并后的数组。
在这些解法中，二分查找法通常是最优的，因为它的时间复杂度是O(log(min(m, n)))，而其他方法的时间复杂度是O(m+n)。
