[数据结构与算法]GO / 图解LeetCode 第四题 Median of Two Sorted Arrays

这道题虽然标记Hard,? 但是看完图解你会觉得超级简单。

关键1. 如何找到中间点，通过连个数组长度和的奇偶数来判断，奇数用中间取两次除以二，偶数中间数字和前一个数字，这样无论什么都可以保证返回两个位置简化程序判断。

关键2. 不用循环完所有数组，更不需要把结构在存到新数组里，只需要找到对应中间点的两个值就好了。所以只需要循环次数和最大的中间点位置一致就可以了。

关键3. 遇到空数组，或者某个数组用完，将数值设置为最大整数，简化判断逻辑

下面看图

?代码:

package _4_test

import (
	"fmt"
	"testing"
)

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	mid1, mid2 := getMidPointers(len(nums1), len(nums2))
	leftIndex, rightIndex := 0, 0
	leftV, rightV := 0,0
	v, v1, v2 := 0, 0, 0
	MAX_INT := 1<<32-1

	for i := 0; i <= mid2; i++ {
		if leftIndex < len(nums1) {
			leftV = nums1[leftIndex]
		}else{
			leftV = MAX_INT
		}
		if rightIndex < len(nums2) {
			rightV = nums2[rightIndex]
		}else{
			rightV = MAX_INT
		}
		fmt.Printf("left: %v / %v right: %v/%v \n", leftIndex, leftV, rightIndex, rightV)
		if leftV <= rightV {
			leftIndex++
			v = leftV
		} else {
			rightIndex++
			v = rightV
		}
		if mid1 == i {
			v1 = v
		}
		if mid2 == i {
			v2 = v
		}
		fmt.Printf("v1/v2: %v/%v \n", v1,v2)
	}

	return float64(v1+v2) / 2.0
}

func getMidPointers(leftLength int, rightLength int) (int, int) {
	sum := leftLength + rightLength
	if sum < 1 {
		return sum, sum
	}
	isOdd := sum % 2 > 0

	mid := sum/2
	if isOdd {
		return mid, mid
	} else {
		return mid-1, mid
	}
}

type Param struct {
	arg1 []int
	arg2 []int
	rs   float64
}

func TestFun(t *testing.T) {
	ps := []Param{
		{
			arg1: []int{1, 3},
			arg2: []int{2},
			rs:   2.0,
		},
		{
			arg1: []int{1, 2},
			arg2: []int{3, 4},
			rs:   2.5,
		},
		{
			arg1: []int{0, 0},
			arg2: []int{0, 0},
			rs:   0.0,
		},
		{
			arg1: []int{},
			arg2: []int{1},
			rs:   1.0,
		},
		{
			arg1: []int{2},
			arg2: []int{},
			rs:   2.0,
		},
	}

	for index, p := range ps {
		temp := findMedianSortedArrays(p.arg1, p.arg2)
		if temp != p.rs {
			t.Error(index, "-Error")
			t.Logf("expect %v, got %v", p.rs, temp)
		} else {
			t.Logf("pass %v", index)
			t.Logf("expect %v, got %v", p.rs, temp)
		}
	}

}