# golang刷LeetCode[0004] 寻找两个有序数组的中位数

#### 题目

https://github.com/betterfor/leetcode-go/tree/master/algorithms/0004_Median_Of_Two_Sorted_Arrays

nums1 = [1,3]
nums2 = [2]

nums1 = [1,2]
nums2 = [3,4]

#### 题解

1、暴力法

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m := len(nums1)
n := len(nums2)
var nums = make([]int,m+n)
// nums1 为空，返回nums2的中位数
if m == 0 {
if n % 2 == 0 {
return float64(nums2[n/2-1] + nums2[n/2]) / 2.0
} else {
return float64(nums2[n/2])
}
}

// nums2 为空，返回nums1的中位数
if n == 0 {
if m % 2 == 0 {
return float64(nums1[m/2-1] + nums1[m/2]) / 2.0
} else {
return float64(nums1[m/2])
}
}

// 将两数组合并
var i,j,count int
for count < m+n {
if i == m {
for j < n {
nums[count] = nums2[j]
j++
count++
}
break
}
if j == n {
for i < m {
nums[count] = nums1[i]
i++
count++
}
break
}

if nums1[i] < nums2[j] {
nums[count] = nums1[i]
i++
count++

} else {
nums[count] = nums2[j]
j++
count++
}
}
if count%2 == 0 {
return float64(nums[count/2-1] + nums[count/2])/2.0
} else {
return float64(nums[count/2])
}
}

2、优化暴力法

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
len1, len2 := len(nums1), len(nums2)
sumLen := len1 + len2
i, j := 0, 0
var left,right int
for k := 0; k < sumLen/2+1; k++ {
left = right
if i < len1 && (j>=len2 || nums1[i] < nums2[j]) {
right = nums1[i]
i++
continue
} else {
right = nums2[j]
j++
}
}

if sumLen & 1 == 0 {
return float64(right + left) / 2.0
} else {
return float64(right)
}
}

3、再优化

Left C Right
a1 a2 ... ai ci ai+1 ... am
b1 b2 ... bj cj bj+1 ... bn

L1:2 / 3 5
L2:1 4 / 7 9

L1:2 3 / 5
L2:1 / 4 7 9

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m,n := len(nums1),len(nums2)
if m > n { // 保证 nums1 最短
return findMedianSortedArrays(nums2,nums1)
}

var nums1Left,nums1Right,nums2Left,nums2Right int
var right = m *2
var left = 0
for left <= right {
c1 := (left + right) / 2
c2 := m + n - c1

if c1 != 0 {
nums1Left = nums1[(c1-1)/2]
} else {
nums1Left = math.MinInt64
}
if c1 != 2 * m {
nums1Right = nums1[c1/2]
} else {
nums1Right = math.MaxInt64
}
if c2 != 0 {
nums2Left = nums2[(c2-1)/2]
} else {
nums2Left = math.MinInt64
}
if c2 != 2 * n {
nums2Right = nums2[c2/2]
} else {
nums2Right = math.MaxInt64
}

if nums1Left > nums2Right {
right = c1 - 1
} else if nums2Left > nums1Right {
left = c1 + 1
} else {
break
}
}

return (math.Max(float64(nums1Left),float64(nums2Left)) + math.Min(float64(nums1Right),float64(nums2Right)))/2.0
}
image

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

#### 题目

https://github.com/betterfor/leetcode-go/tree/master/algorithms/0004_Median_Of_Two_Sorted_Arrays

nums1 = [1,3]
nums2 = [2]

nums1 = [1,2]
nums2 = [3,4]

#### 题解

1、暴力法

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m := len(nums1)
n := len(nums2)
var nums = make([]int,m+n)
// nums1 为空，返回nums2的中位数
if m == 0 {
if n % 2 == 0 {
return float64(nums2[n/2-1] + nums2[n/2]) / 2.0
} else {
return float64(nums2[n/2])
}
}

// nums2 为空，返回nums1的中位数
if n == 0 {
if m % 2 == 0 {
return float64(nums1[m/2-1] + nums1[m/2]) / 2.0
} else {
return float64(nums1[m/2])
}
}

// 将两数组合并
var i,j,count int
for count < m+n {
if i == m {
for j < n {
nums[count] = nums2[j]
j++
count++
}
break
}
if j == n {
for i < m {
nums[count] = nums1[i]
i++
count++
}
break
}

if nums1[i] < nums2[j] {
nums[count] = nums1[i]
i++
count++

} else {
nums[count] = nums2[j]
j++
count++
}
}
if count%2 == 0 {
return float64(nums[count/2-1] + nums[count/2])/2.0
} else {
return float64(nums[count/2])
}
}

2、优化暴力法

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
len1, len2 := len(nums1), len(nums2)
sumLen := len1 + len2
i, j := 0, 0
var left,right int
for k := 0; k < sumLen/2+1; k++ {
left = right
if i < len1 && (j>=len2 || nums1[i] < nums2[j]) {
right = nums1[i]
i++
continue
} else {
right = nums2[j]
j++
}
}

if sumLen & 1 == 0 {
return float64(right + left) / 2.0
} else {
return float64(right)
}
}

3、再优化

Left C Right
a1 a2 ... ai ci ai+1 ... am
b1 b2 ... bj cj bj+1 ... bn

L1:2 / 3 5
L2:1 4 / 7 9

L1:2 3 / 5
L2:1 / 4 7 9

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m,n := len(nums1),len(nums2)
if m > n { // 保证 nums1 最短
return findMedianSortedArrays(nums2,nums1)
}

var nums1Left,nums1Right,nums2Left,nums2Right int
var right = m *2
var left = 0
for left <= right {
c1 := (left + right) / 2
c2 := m + n - c1

if c1 != 0 {
nums1Left = nums1[(c1-1)/2]
} else {
nums1Left = math.MinInt64
}
if c1 != 2 * m {
nums1Right = nums1[c1/2]
} else {
nums1Right = math.MaxInt64
}
if c2 != 0 {
nums2Left = nums2[(c2-1)/2]
} else {
nums2Left = math.MinInt64
}
if c2 != 2 * n {
nums2Right = nums2[c2/2]
} else {
nums2Right = math.MaxInt64
}

if nums1Left > nums2Right {
right = c1 - 1
} else if nums2Left > nums1Right {
left = c1 + 1
} else {
break
}
}

return (math.Max(float64(nums1Left),float64(nums2Left)) + math.Min(float64(nums1Right),float64(nums2Right)))/2.0
}
image