004_寻找两个正序数组的中位数

知识点：二分、尾递归、中位数

LeetCode第四题：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/

语言：GoLang

// 朴素版：遍历至第k / 2个数，即为答案。时间复杂度O((m+n)/2)，即O(m+n)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    len1 := len(nums1)
    len2 := len(nums2)

    head, head1, head2 := 0, 0, 0
    if len1 == 0 {
        head = nums2[head2]
    }else if len2 == 0 {
        head = nums1[head1]
    }else {
        if nums1[head1] > nums2[head2] {
            head = nums2[head2]
        }else {
            head = nums1[head1]
        }
    }


    midPos := (len1 + len2) / 2
    for i := 0; i < midPos; i++ {
        head, head1, head2 = getHeader(nums1, nums2, head1, head2)
    }

    if (len1 + len2) & 1 == 1 {
        head, head1, head2 = getHeader(nums1, nums2, head1, head2)
        return float64(head)
    }else {
        tmp := float64(head)
        head, head1, head2 = getHeader(nums1, nums2, head1, head2)
        return (float64(head) + tmp) / 2
    }

    return 0.0
}

func getHeader(nums1 []int, nums2 []int, head1 int, head2 int) (int, int, int) {
    if head1 >= len(nums1) {
        return nums2[head2], head1, head2 + 1
    }

    if head2 >= len(nums2) {
        return nums1[head1], head1 + 1, head2
    }

    if nums1[head1] > nums2[head2] {
        return nums2[head2], head1, head2 + 1
    }else {
        return nums1[head1], head1 + 1, head2
    }
}




// 优化版：转化为第k小的数，二分解法，时间复杂度O(log(m+n))
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	len1 := len(nums1)
	len2 := len(nums2)

	left := Kth(nums1, nums2, (len1 + len2 + 1) / 2)
	right := Kth(nums1, nums2, (len1 + len2 + 2) / 2)

	return float64(left + right) / 2
}

func Kth(nums1 []int, nums2 []int, k int) int {
	// 始终让nums2指向较短的数组，简化后面操作
	if len(nums1) < len(nums2) {
		nums1, nums2 = nums2, nums1
	}

	if len(nums2) == 0 {
		if len(nums1) == 0 {
			return 0
		}
		return nums1[ k - 1 ]
	}

	// 递归出口
	if k == 1 {
		return min(nums1[0], nums2[0])
	}

	// len(nums2) 必小于 len(nums1)
	pos := min(len(nums2), k / 2)
	if nums1[pos - 1] > nums2[pos - 1] {
		return Kth(nums1, nums2[pos: ], k - pos)
	}else {
		return Kth(nums1[pos: ], nums2, k - pos)
	}
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

004_寻找两个正序数组的中位数

原文：https://www.cnblogs.com/cenyol/p/13211993.html