前言

開始刷leetcode，保證平均每天一道題吧，學學別人的思路，提高編程技術。

目錄

文章目錄

• 前言
• 目錄
• 正文
• 問題3：尋找兩個有序數組的中位數
• 舉例
• 分析

正文

繼續刷題

問題3：尋找兩個有序數組的中位數

給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。

請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為 O(log(m + n))。

你可以假設 nums1 和 nums2 不會同時為空。

舉例

nums1 = [1,2,3]
nums2 = [2]
則中位數是 2.0

分析

這個問題很難，因為，有時間要求，因此，不能使用暴力破解方法。

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]):n1 = len(nums1)n2 = len(nums2)if n1 > n2:return self.findMedianSortedArrays(nums2,nums1)k = (n1 + n2 + 1)//2left = 0right = n1while left < right :m1 = left +(right - left)//2m2 = k - m1if nums1[m1] < nums2[m2-1]:left = m1 + 1else:right = m1m1 = leftm2 = k - m1 c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )if (n1 + n2) % 2 == 1:return c1c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf"))return (c1 + c2) / 2

總結

以上是生活随笔為你收集整理的leetcode刷题实录：4的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。