[leetcode-in-go] 0004-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)).

You may assume nums1 and nums2 cannot be both empty.

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

解题思路

首先会想到 归并排序的归并过程，一半归并完成即可，但不符合 log(m+n) 时间复杂度要求

下边是归并方法解题代码，leetcode 提交会通过，可见并没有严格检查时间复杂度

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {

	i1, len1, i2, len2 := 0, len(nums1), 0, len(nums2)

	lenAll := len1 + len2

	if lenAll == 0 {
		return 0
	}

	// 类似快慢指针，记录中位数
	slow, quick := 0, 0

	for i := 0; i <= lenAll/2; i++ {
		slow = quick
		if i1 == len1 || (i1 < len1 && i2 < len2 && nums1[i1] >= nums2[i2]) {
			quick = nums2[i2]
			i2++
			continue
		}
		if i2 == len2 || (i1 < len1 && i2 < len2 && nums1[i1] <= nums2[i2]) {
			quick = nums1[i1]
			i1++
		}
	}

	if lenAll%2 == 0 {
		return float64(slow+quick) / 2.0
	}

	return float64(quick)
}
           

仔细思考，既然复杂度是 log(m+n) 这种形式的，跑不了二分查找了

解题的关键定理：

求有序数组 A 和 B 有序合并之后第 k 小的数，如果 A[k/2-1] < B[k/2-1]，那么 A[0] ~ A[k/2-1] 一定在第 k 小的数的序列当中

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func findKth(nums1, nums2 []int, k int) int {

    // 总是假设 nums1 数组较短
	if len(nums1) > len(nums2) {
		return findKth(nums2, nums1, k)
	}

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

	if k == 1 {
		return min(nums1[0], nums2[0])
	}
	// 保证 p1 有效
	p1 := min(k/2, len(nums1))
	p2 := k - p1

	if nums1[p1-1] < nums2[p2-1] {
		return findKth(nums1[p1:], nums2, k-p1)
	} else if nums1[p1-1] > nums2[p2-1] {
		return findKth(nums1, nums2[p2:], k-p2)
	} else {
		return nums1[p1-1]
	}

}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	total := len(nums1) + len(nums2)
	if total%2 != 0 {
		return float64(findKth(nums1, nums2, total/2+1))
	} else {
		m := float64(findKth(nums1, nums2, total/2))
		n := float64(findKth(nums1, nums2, total/2+1))
		return (m + n) / 2
	}
}