題目

描述

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

示例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

提示

（1）nums1.length == m
（2）nums2.length == n
（3）0 <= m <= 1000
（4）0 <= n <= 1000
（5）1 <= m + n <= 2000
（6）-106 <= nums1[i], nums2[i] <= 106

進階

你能設計一個時間復雜度為 O(log (m+n)) 的演算法解決此問題嗎？

解題思路

（1）將兩個串列進行合并

（2）通過sort函式進行排序

（3）判斷兩個串列合并后的長度

（4）長度位奇數，那么中位數的index 為(len_list + 1) / 2

（5）長度為偶數的話，那么中位數的index為 len_list / 2

代碼

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        num_list = nums1 + nums2
        num_list.sort()
        print(num_list)
        if len(num_list)%2==0:
            index = int(len(num_list)/2)
            return  (num_list[index] + num_list[index-1])/2
        else:
            index = int((len(num_list)-1)/2)
            return  num_list[index]

進階

（1）二分法查找

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKthElement(k):
            """
            - 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較
            - 這里的 "/" 表示整除
            - nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個
            - nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個
            - 取 pivot = min(pivot1, pivot2)，兩個陣列中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個
            - 這樣 pivot 本身最大也只能是第 k-1 小的元素
            - 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素，把這些元素全部 "洗掉"，剩下的作為新的 nums1 陣列
            - 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素，把這些元素全部 "洗掉"，剩下的作為新的 nums2 陣列
            - 由于我們 "洗掉" 了一些元素（這些元素都比第 k 小的元素要小），因此需要修改 k 的值，減去洗掉的數的個數
            """
            
            index1, index2 = 0, 0
            while True:
                # 特殊情況
                if index1 == m:
                    return nums2[index2 + k - 1]
                if index2 == n:
                    return nums1[index1 + k - 1]
                if k == 1:
                    return min(nums1[index1], nums2[index2])

                # 正常情況
                newIndex1 = min(index1 + k // 2 - 1, m - 1)
                newIndex2 = min(index2 + k // 2 - 1, n - 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
        
        m, n = len(nums1), len(nums2)
        totalLength = m + n
        if totalLength % 2 == 1:
            return getKthElement((totalLength + 1) // 2)
        else:
            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2

（2）劃分陣列

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)

        infinty = 2**40
        m, n = len(nums1), len(nums2)
        left, right = 0, m
        # median1：前一部分的最大值
        # median2：后一部分的最小值
        median1, median2 = 0, 0

        while left <= right:
            # 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            # // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            i = (left + right) // 2
            j = (m + n + 1) // 2 - i

            # nums_im1, nums_i, nums_jm1, nums_j 分別表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            nums_im1 = (-infinty if i == 0 else nums1[i - 1])
            nums_i = (infinty if i == m else nums1[i])
            nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
            nums_j = (infinty if j == n else nums2[j])

            if nums_im1 <= nums_j:
                median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
                left = i + 1
            else:
                right = i - 1

        return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1

Reference

題庫 - 力扣 (LeetCode) 全球極客摯愛的技術成長平臺