Median Of Two Sorted Arrays

本篇文章是对leetcode中Median Of Two Sorted Arrays解法的整理。

image.png

二分查找

在大家读题的时候不知有没有注意两个小细节“O(log(m+n))”和“Sorted Arrays”。经常刷题的同学可能很容易想到这个不就是二分查找吗。所以我们撇开这题不谈，先看看二分查找。

给定一个有序数组a = [1,3,5,7,9,10,11,13,14,15]，如果快速找到数字11的位置。

如果确定是长度很短的数组，我建议大家直接遍历就行了。但是在项目中这么理想的情况很少存在，我们经常需要处理长度特别长的数组，这时候遍历可能就有点吃不消了。于是一种优化的方法自然成了我们追求的目标，这里给出二分查找的方法。

上面给出的数组是有序的，那么如果把数组在中间一分为二，那是不是意味着我们只需要对左侧数组的最大值（最后一个数字）和右侧数组的最小值（第一个数组）比较，就可以判断目标值11在左半边还是右半边。

采用相同的方法在确定的小数组中继续一分为二并判断，直到找到目标值。

这就是二分查找，来张图演示一下：

image.png

Golang代码（非递归）：

func BinarySearch(arr []int, target int)(index int) {
    leftIndex, rightIndex := 0, len(arr) - 1
    for {
        if leftIndex > rightIndex { // 未找到的退出条件
            index = -1
            break
        }
        middleIndex := (leftIndex + rightIndex) / 2
        if arr[middleIndex] == target { // 找到的退出条件
            index = middleIndex
            break
        } else if arr[middleIndex] > target { //取左侧一半数组
            rightIndex = middleIndex - 1
        } else { //取右侧一半的数组
            leftIndex = middleIndex + 1
        }
    }
    return
}

Golang代码（递归）：

func BinarySearch(arr []int, target int)(index int) {
    leftIndex, rightIndex := 0, len(arr) - 1
    return recursive(arr, leftIndex, rightIndex, target)
}
func recursive(arr []int, leftIndex, rightIndex, target int) int {
    if leftIndex > rightIndex { // 未找到的退出条件
        return -1
    }
    middleIndex := (leftIndex + rightIndex) / 2
    if arr[middleIndex] == target { // 找到的退出条件
        return middleIndex
    } else if arr[middleIndex] > target { //取左侧一半数组
        return recursive(arr, leftIndex, middleIndex - 1, target)
    } else { //取右侧一半的数组
        return recursive(arr, middleIndex + 1, rightIndex, target)
    }
}

测试：

func main() {
    arr := []int{1,3,5,6,9,10,11,13,14,15}
    target := 7
    fmt.Println(BinarySearch(arr, target))
}

解题思路

从题目中我们可以看出核心问题是寻找两个数组中第K个数，K为两个数组中间的一个（数组之和为奇数）或两个数（数组之后为偶数），即：
$\begin{cases} k =（length + 1）/ 2 & length是奇数 \\ k1 = length / 2， k2 = （length + 1）/ 2 & length是偶数 \end{cases}$

我们以下面一组case为例：

image.png

我们需要找到第7和第8个数，求平均。这里我们以第7个数为例进行说明。

首先我们先查找k/2=7/2=3个数据，比较两个数组的第三个元素的大小，我们发现5 < 8，于是我们删除第一个数组的前三个元素。

image.png

这里可能有人会问为什么删除第一个数组？因为我们需要保证删除的数据尽可能小，删除了5之后我们可以保证剩余数组中>=5的数的数量会大于整体长度的一半。在这个例子中大于等于5的元素的数量可以确定至少有(9+5)-3-2=9个，其中3是nums1中删除的元素数，2是nums中小于8的元素数。这样可以保证目标值不会被删除。

删除3个元素后，问题变成了寻找第k=7-3=4个元素。采用同样的方式：

image.png

我们删除4的一半个元素，即删除nums2中前2个元素。继续采用同样的方法删除剩余的2个元素中的一半：

image.png

当k=1时，我们只需要取两个数组第一个元素中较小的元素即可。

image.png

同时，我们需要注意两种边界问题：

当其中一个数组长度为0时，我们可以直接在另一个数组中获取目标值。
当其中一个数组长度小于k/2时，我们可以比较这个数组的最后一个元素。

源代码（Golang）

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if (len(nums1) + len(nums2)) % 2 == 0 {
        return float64(
            findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2) + 
            findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2 + 1)) / 2.0
    }
    return float64(findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2 + 1))
}

func findKth(nums1, nums2 []int, k int) int {
    if len(nums1) == 0 {
        return nums2[k - 1]
    }
    if len(nums2) == 0 {
        return nums1[k - 1]
    }
    if k == 1 {
        return min(nums1[0], nums2[0])
    }
    var num1 int
    var num2 int
    var to1 int
    var to2 int
    if k / 2 > len(nums1) {
        num1 = nums1[len(nums1) - 1]
        to1 = len(nums1)
    } else {
        num1 = nums1[k / 2 - 1]
        to1 = k / 2
    }
    if k / 2 > len(nums2) {
        num2 = nums2[len(nums2) - 1]
        to2 = len(nums2)
    } else {
        num2 = nums2[k / 2 - 1]
        to2 = k / 2
    }
    if num1 > num2 {
        return findKth(nums1, nums2[to2:], k - to2)
    }
    return findKth(nums1[to1:], nums2, k - to1)
}

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