4. 尋找兩個正序數組的中位數、Leetcode的Go實作

​​4. 尋找兩個正序數組的中位數​​

給定兩個大小分别為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出并傳回這兩個正序數組的 中位數 。

算法的時間複雜度應該為 O(log (m+n)) 。

示例 1：

輸入：nums1 = [1,3], nums2 = [2]

輸出：2.00000

解釋：合并數組 = [1,2,3] ，中位數 2

示例 2：

輸入：nums1 = [1,2], nums2 = [3,4]

輸出：2.50000

解釋：合并數組 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5

示例 3：

輸入：nums1 = [0,0], nums2 = [0,0]

輸出：0.00000

示例 4：

輸入：nums1 = [], nums2 = [1]

輸出：1.00000

示例 5：

輸入：nums1 = [2], nums2 = []

輸出：2.00000

提示：

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-106 <= nums1[i], nums2[i] <= 106

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    nums1=append(nums1,nums2...)
    sort.Ints(nums1)
    if len(nums1)%2!=0{
        return float64(nums1[(len(nums1)-1)/2])
    }
    return float64(nums1[(len(nums1)-1)/2]+nums1[(len(nums1))/2])/2
}      

• 如果A[k/2-1]或者B[k/2−1] 越界，那麼我們可以選取對應數組中的最後一個元素。在這種情況下，我們必須根據排除數的個數減少 k 的值，而不能直接将 k 減去 k/2.
• 如果一個數組為空，說明該數組中的所有元素都被排除，我們可以直接傳回另一個數組中第 k 小的元素。
• 如果 k=1，我們隻要傳回兩個數組首元素的最小值即可。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    totalLength := len(nums1) + len(nums2)
    if totalLength%2 == 1 {
        midIndex := totalLength/2
        return float64(getKthElement(nums1, nums2, midIndex + 1))
    } else {
        midIndex1, midIndex2 := totalLength/2 - 1, totalLength/2
        return float64(getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0
    }
    return 0
}

func getKthElement(nums1, nums2 []int, k int) int {
    index1, index2 := 0, 0
    for {
        if index1 == len(nums1) {
            return nums2[index2 + k - 1]
        }
        if index2 == len(nums2) {
            return nums1[index1 + k - 1]
        }
        if k == 1 {
            return min(nums1[index1], nums2[index2])
        }
        half := k/2
        newIndex1 := min(index1 + half, len(nums1)) - 1
        newIndex2 := min(index2 + half, len(nums2)) - 1
        pivot1, pivot2 := nums1[newIndex1], nums2[newIndex2]
        if pivot1 <= pivot2 {
            k -= (newIndex1 - index1 + 1)
            index1 = newIndex1 + 1
        } else {
            k -= (newIndex2 - index2 + 1)
            index2 = newIndex2 + 1
        }
    }
    return 0
}

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