Description

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)).

nums1 = [1, 3]
nums2 = [2]

The median is 2.0 
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


Ideas

這題的難點在於空間複雜度被限制於O(log(m + n)),也就是說要在兩個有序array之間使用二分法來取得中位數。

假設mn分別是兩個array的長度,不論m + n是奇數或偶數,中位數都可以是(m + n + 1)/2(m + n + 2)/2的平均值。

可以定義一個function去找到兩個array的第(m + n + 1)/2個值和第(m + n + 2)/2個值,再求這兩個值的平均。

可以利用兩個pointer分別紀錄兩個array的起始位置以避免產生新的array而增加時間複雜度。

這道題的二分法的重點在對k(即(m + n + 1)/2(m + n + 2)/2)來做二分,也就是分別在兩個array中找第k/2的值。

若array包含第k/2的值的話取出,若沒有的話則賦予int32的極大值,之後比較兩個array的第k/2的值。

若第一個array的值小於第二個array的值的話,則可以確定目標值不再第一個array的前k/2

即去掉第一個array的前k/2的值進行下一輪比較。

若是第二個array的值比較小的話,則去掉第二個array的前k/2的值進行下一輪比較。


Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func findKth(nums1 []int, i int, nums2 []int, j int, k int) float64 {
    if i >= len(nums1) {
        return float64(nums2[j + k - 1])
    }
    if j >= len(nums2) {
        return float64(nums1[i + k - 1])
    }
    if k == 1 {
        return math.Min(float64(nums1[i]), float64(nums2[j]))
    }
    midVal1 := math.MaxInt32
    midVal2 := math.MaxInt32

    if i + k/2 - 1 < len(nums1) {
        midVal1 = nums1[i + k/2 - 1]
    }
    if j + k/2 - 1 < len(nums2) {
        midVal2 = nums2[j + k/2 - 1]
    }
    if midVal1 < midVal2 {
        return findKth(nums1, i + k/2, nums2, j, k - k/2)
    } else {
        return findKth(nums1, i, nums2, j + k/2, k - k/2)
    }
    
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m := len(nums1)
    n := len(nums2)
    left := (m + n + 1)/2
    right := (m + n + 2)/2
        
    return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right))/2.0
}