Golang 基礎
- [4. Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)
-
- 題目
- 解題思路
- 解決方案
-
- 1. append
- 2. 非append 自己合并
- 3. 4ms 解決範例
- 參考編寫測試程式
- 總結
鳴謝： LeetCode-In-Go
4. Median of Two Sorted Arrays
題目
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
解題思路
輸入兩個已經排序好的整數切片，合并兩個切片，傳回合并後切片的中位數。
是以，題目的關鍵是，如何高效地合并切片。
個人認為的解題步驟可以分為：
- 判斷并合并兩個數組，一個個元素來處理，不要直接使用append合并兩個數組
- 合并之後，補全每個數組還剩下的部分，解決兩個數組長短不一的問題
- 判斷計算結果的長度，根據奇偶性來處理傳回結果。
解決方案
1. append
直接用append方法進行合并，然後使用sort方法對内容進行排序，這種方式的效率不高。
具體實作的代碼如下：
// Solution by Panda.
// 生成一個新的數組，然後判斷長度奇偶數，取中間值。
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
if len(nums1) == 0 {
if len(nums2) % 2 == 0 {
return float64((nums2[len(nums2)/2] + nums2[len(nums2)/2 - 1])) / 2.0
} else {
return float64(nums2[len(nums2)/2])
}
}
if len(nums2) == 0 {
if len(nums1) % 2 == 0 {
return float64((nums1[len(nums1)/2] + nums1[len(nums1)/2 - 1])) / 2.0
} else {
return float64(nums1[len(nums1)/2])
}
}
nums := append(nums1, nums2...)
// 對數組進行排序
sort.Ints(nums)
if len(nums) % 2 == 0 {
return float64((nums[len(nums)/2] + nums[len(nums)/2 - 1])) / 2.0
} else {
return float64(nums[len(nums)/2])
}
}
2. 非append 自己合并
下面這種自己合并的效率和本身的append差不多。
// Solution by Panda.
// 生成一個新的數組，然後判斷長度奇偶數，取中間值。
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
nums := combine(nums1, nums2)
return medianOf(nums)
}
func combine(mis, njs []int) []int {
lenMis, i := len(mis), 0
lenNjs, j := len(njs), 0
res := make([]int, lenMis+lenNjs)
for k := 0; k < lenMis+lenNjs; k++ {
if i == lenMis ||
(i < lenMis && j < lenNjs && mis[i] > njs[j]) {
res[k] = njs[j]
j++
continue
}
if j == lenNjs ||
(i < lenMis && j < lenNjs && mis[i] <= njs[j]) {
res[k] = mis[i]
i++
}
}
return res
}
func medianOf(nums []int) float64 {
l := len(nums)
if l == 0 {
panic("切片長度為0， 無法求解中位數.")
}
if l%2 == 0 {
return float64(nums[l/2]+nums[l/2-1]) / 2.0
}
return float64(nums[l/2])
}
3. 4ms 解決範例
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
var newArray []int
i:=0
j:=0
for ; i<len(nums1)&&j<len(nums2);{
if nums1[i]<nums2[j] {
newArray=append(newArray, nums1[i])
i++
} else if nums1[i]==nums2[j] {
newArray=append(newArray, nums1[i])
newArray=append(newArray, nums2[j])
i++
j++
} else {
newArray=append(newArray, nums2[j])
j++
}
}
if i < len(nums1) {
newArray = append(newArray, nums1[i:len(nums1)]...)
}
if j < len(nums2) {
newArray = append(newArray, nums2[j:len(nums2)]...)
}
length := len(newArray)
if len(newArray) % 2 == 0{
return float64((newArray[length/2-1] + newArray[length/2]))/2
} else {
return float64(newArray[length/2])
}
}
參考編寫測試程式
package problem0004
import (
"testing"
"github.com/stretchr/testify/assert"
)
type para struct {
one []int
two []int
}
type ans struct {
one float64
}
type question struct {
p para
a ans
}
func Test_OK(t *testing.T) {
ast := assert.New(t)
qs := []question{
question{
p: para{
one: []int{1, 3},
two: []int{2},
},
a: ans{
one: 2,
},
},
question{
p: para{
one: []int{1, 3},
two: []int{2, 4},
},
a: ans{
one: 2.5,
},
},
}
for _, q := range qs {
a, p := q.a, q.p
ast.Equal(a.one, findMedianSortedArrays(p.one, p.two), "輸入:%v", p)
}
ast.Panics(func() { findMedianSortedArrays([]int{}, []int{}) }, "對空切片求中位數，卻沒有panic")
}
總結
分步驟完成程式。