<input id="0qass"><u id="0qass"></u></input>
  • <input id="0qass"><u id="0qass"></u></input>
  • <menu id="0qass"><u id="0qass"></u></menu>

    算法題:尋找兩個正序數組的中位數

    算法題 專欄收錄該內容
    28 篇文章 0 訂閱

    算法題:尋找兩個正序數組的中位數

    題目描述

    給定兩個大小為 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
    

    代碼

    class Solution:
        def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
            new_num = []
            i, j = 0, 0
            num_len = len(nums1) + len(nums2)
            print(num_len)
            while len(new_num) <= num_len / 2 :
                print(i,j)
                if i == len(nums1):
                    new_num.append(nums2[j])
                    j+=1
                elif j == len(nums2):
                    new_num.append(nums1[i])
                    i+=1
                else:
                    if nums1[i] < nums2[j]:
                        new_num.append(nums1[i])
                        i += 1
                    else:
                        new_num.append(nums2[j])
                        j += 1
            print(new_num)
            if num_len % 2 == 0:
                return (new_num[num_len//2-1] + new_num[num_len//2])/2
            else:
                return new_num[(num_len-1)//2]
    

    執行效率

    2091 個測試用例
    執行用時: 136 ms
    內存消耗: 12.9 MB

    解題思路及代碼來源:博主
    題目來源:力扣(LeetCode)
    題目鏈接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays
    題目著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

    • 8
      點贊
    • 2
      評論
    • 7
      收藏
    • 一鍵三連
      一鍵三連
    • 掃一掃,分享海報

    ??2020 CSDN 皮膚主題: 程序猿惹誰了 設計師:白松林 返回首頁
    實付
    使用余額支付
    點擊重新獲取
    掃碼支付
    錢包余額 0

    抵扣說明:

    1.余額是錢包充值的虛擬貨幣,按照1:1的比例進行支付金額的抵扣。
    2.余額無法直接購買下載,可以購買VIP、C幣套餐、付費專欄及課程。

    余額充值
    多乐彩