本篇文章是對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爲兩個數組中間的一個（數組之和爲奇數）或兩個數（數組之後爲偶數），即：

我們以下面一組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

同時，我們需要注意兩種邊界問題：

  1. 當其中一個數組長度爲0時，我們可以直接在另一個數組中獲取目標值。
  2. 當其中一個數組長度小於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
}

有疑問加站長微信聯繫

相關文章