題目
給定兩個大小分別為m,n的正序(從小到大)的數(shù)組nums1和nums2,請你找出并返回這兩個數(shù)組的中位數(shù)。
算法的時間復(fù)雜度應(yīng)該為 O(log (m+n))
示例：
輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數(shù)組 = [1,2,3] 绅喉，中位數(shù) 2
輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數(shù)組 = [1,2,3,4] 轴踱，中位數(shù) (2 + 3) / 2 = 2.5
分析
- 如何合并兩個有序數(shù)組?
- 如何確定中位數(shù)?
第一個問題吏够，歸并排序算法
第二個問題抡草，如果合并后的數(shù)組為奇數(shù)觅赊，則取(len(arr)-1)/2一位數(shù)下標(biāo)對應(yīng)元素取中位數(shù)，如果為偶數(shù)位捉邢，則取(len(arr))/2, len(arr)/2+1兩位數(shù)下標(biāo)對應(yīng)元素取中位數(shù)脯丝。
// 歸并排序
// 合并兩個有序數(shù)組
func merge(left, right []int) []int {
var result []int
for len(left) > 0 || len(right) > 0 {
if len(left) > 0 && len(right) > 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
} else if len(left) > 0 {
result = append(result, left[0])
left = left[1:]
} else if len(right) > 0 {
result = append(result, right[0])
right = right[1:]
}
fmt.Println("result:", result)
}
return result
}
思路
依次從兩個數(shù)組中取出一個數(shù)，進(jìn)行比較伏伐，較小值放入目標(biāo)數(shù)組宠进，同時在原數(shù)組中剔除該元素，直到其中一邊數(shù)組個數(shù)為空藐翎，一邊任然存在元素材蹬，然后將剩余的元素一一加入目標(biāo)數(shù)組，最終待所有元素都添加完成吝镣，整個排序過程也完成堤器。
該算法復(fù)雜度為O(log(m+n))，滿足題目要求赤惊。
完整代碼如下：
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
var result []int
var mid float64
for len(nums1) > 0 || len(nums2) > 0 {
if len(nums1) > 0 && len(nums2) > 0 {
if nums1[0] < nums2[0] {
result = append(result, nums1[0])
nums1 = nums1[1:]
} else {
result = append(result, nums2[0])
nums2 = nums2[1:]
}
} else if len(nums1) > 0 {
result = append(result, nums1[0])
nums1 = nums1[1:]
} else if len(nums2) > 0 {
result = append(result, nums2[0])
nums2 = nums2[1:]
}
}
n := len(result)
if n%2 == 0 {
// 此處需注意類型轉(zhuǎn)換
mid = float64(result[n/2-1]+result[n/2]) / 2
} else {
mid = float64((result[n/2]))
}
return mid
}
在該題中用的歸并算法并非完整的歸并排序算法，只算其中的一部分凰锡，如果考慮原數(shù)組是一個無序數(shù)組未舟，我們需要對數(shù)組進(jìn)行拆分圈暗，使用遞歸排序并進(jìn)行合并。算法代碼如下：
func mergeSort(arr []int) []int {
var result []int
mid := len(arr)/2
left := arr[:mid]
right := arr[mid:]
left := mergeSort(left)
right := mergeSort(right)
result = merge(left, right)
return result
}
分析一下整個過程裕膀，算法中包含一個遞歸员串，這是為什么呢？
歸并排序算法的本質(zhì)是一種分治思想昼扛，通過局部的合并寸齐，一層一層遞歸到整個數(shù)組的合并。
首先我們將數(shù)組進(jìn)行左右拆分抄谐，拆分點(diǎn)是可以隨意選擇的渺鹦，我們這里選擇了中間位置，最終我們將數(shù)組拆分成了只有一個數(shù)的左右數(shù)組蛹含，這時候比較大小非常容易了毅厚。
然后我們進(jìn)行逆推，第一層（遞歸的初始層）通過merge方法進(jìn)行了合并, 我們可以看到left浦箱，right數(shù)組這個時候的值是調(diào)用了上一次mergeSort之后的返回值吸耿，于是我們需要將此次merge的結(jié)果返回，這時我們得到了第二層的left酷窥，right數(shù)組咽安，同樣也需要進(jìn)行依次merge，
依次倒推我們最終得到了排好序的目標(biāo)數(shù)組蓬推，整個過程非常簡潔妆棒。
