[leetcode algorithms]題目4

02-12

4. Median of Two Sorted Arrays

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

Example 1:

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

Example 2:

Example 2: nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5

自己寫的代碼：

第一版演算法複雜度O(n)

兩個列表結尾都append一個正無窮作為哨兵，這樣就不需要判斷列表是否為空。從i=0開始，不停地將兩個列表首個元素的較小者pop出來，直到i=兩個數組總長度的一半為止。判斷總長度是奇數還是偶數，返回結果。運行時間205 ms。

class Solution: def findMedianSortedArrays(self, nums1, nums2): a = len(nums1) b = len(nums2) k = 0 n, m = divmod(a + b, 2) nums1.append(float(inf)) nums2.append(float(inf)) for i in range(n): if nums1[0] < nums2[0]: k = nums1.pop(0) else: k = nums2.pop(0) res = min(nums1[0], nums2[0]) if m is 0: res = (k + res) / 2 return res

第二版演算法複雜度O(logn)

兩個列表結尾都append一個正無窮作為哨兵，首部append一個負無窮作為哨兵。利用二分查找的思想尋找數組1的標號，根據兩個數組總長度的一半減去數組1的標號i1得到數組2的標號i2。滿足nums1[i1] < nums2[i2+1]且nums2[i2] < nums1[i1+1]時循環停止。運行時間205 ms。

class Solution: def findMedianSortedArrays(self, nums1, nums2): nums1.append(float(inf)) nums2.append(float(inf)) nums1.insert(0, -float(inf)) nums2.insert(0, -float(inf)) l1, l2 = len(nums1), len(nums2) n, odd = divmod(l1 + l2, 2) low = 0 high = l1 - 1 while(low <= high): i1 = (low + high) // 2 i2 = n - i1 - 2 if i2 < -1: high = i1 - 1 elif i2 > l2 - 1: low = i1 + 1 elif i2 is not l2 - 1 and nums1[i1] > nums2[i2+1]: high = i1 - 1 elif i2 is not -1 and nums2[i2] > nums1[i1+1]: low = i1 + 1 else: break if odd: res = min(nums1[i1+1], nums2[i2+1]) else: res = (max(nums1[i1], nums2[i2]) + min(nums1[i1+1], nums2[i2+1])) / 2 return res

受討論區啟發後寫的代碼：

評論區的高票代碼思路跟我的一致（開心^^），所以這段就不寫了。