Golang学习之路 - LeetCode-Go-Learning 第四题.寻找两个有序数组的中位数

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
           

解题思路

输入两个已经排序好的整数切片，合并两个切片，返回合并后切片的中位数。

所以，题目的关键是，如何高效地合并切片。

个人认为的解题步骤可以分为：

1. 判断并合并两个数组，一个个元素来处理，不要直接使用append合并两个数组
2. 合并之后，补全每个数组还剩下的部分，解决两个数组长短不一的问题
3. 判断计算结果的长度，根据奇偶性来处理返回结果。

解决方案

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")
}

           

总结

分步骤完成程序。