[LeetCode]題解（python）：004-MedianofTwoSortedArrays

2019-11-14 17:01:28

字體：大中小

來源：轉載

供稿：網友

題目來源：

https://leetcode.com/PRoblems/median-of-two-sorted-arrays/

題意分析:

這道題目是輸入兩個已經排好序的數組（長度為m,n），將這兩個數組整合成一個數組，輸出新數組的中位數。要求時間復雜度是（log（m + n）。比如如果輸入[1,2,3]，[3,4,5]。那么得到的新數組為[1,2,3,3,4,5]得到的中位數就是3.

題目思路：

由于題目要求的時間復雜度是（log（m+n))，如果我們直接把兩個數組整合一起，那么時間復雜度肯定超過（log（m+n））。所以整理肯定是不行的。那么還有什么方法嗎？答案是肯定的。

首先我們要先了解中位數的概念，中位數就是有序數組的中間那個數。那么如果我們將比中位數小的數和比中位數大的數去掉同樣的個數，中位數的值也不會變化（數組的個數為偶數的時候另外討論，因為那時候中位數是中間兩個數的平均值，所以中位數旁邊兩個數不能去掉）。

所以我們不妨試著將數組長度不斷縮短。這里不妨提出一個引理。假設有兩個有序數組a_m，b_n，他們整合后的有序數組為c_n+m。他們的中位數分別是a_m_/2,b_n_/2,c_(m+n)/2。如果a_m_/2 < b_n_/2,則 a₀_…m/2 <= c_(m+n)/2 <= b_n_{/2…n 。}

引理證明：

假設 a_m/2 > c_(m+n)/2 ，那么 b_n_/2> c_(m+n)/2，所以在數組a_m里有大于m/2個數大于c_(m+n)/2，在數組b_n里也有n/2個數大于c_(m+n)/2

也就是說在c_n+m里有（m+n）/2個數大于c_(m+n)/2，此時就c_(m+n)/2不再是數組c_n+m的中位數。

所以a₀_…m/2 <= c_(m+n)/2。

同理可得c_(m+n)/2 <= b_n_/2…n。

根據上述引理，我們不妨設m>n，那么我們根據判斷兩個數組的中位數大小，每個數組每次減少n/2長度，直到n為1。如此，我們通過減少log（n）次可以得到答案。這種方法的時間復雜度是（log（min（m,n）））。

代碼（python）：

 1 class Solution(object): 2     def getMedian(self,nums): 3         size = len(nums) 4         if size == 0: 5             return [0,0] 6         if size % 2 == 1: 7             return [nums[size // 2],size // 2] 8         return [(float(nums[size // 2 - 1] + nums[size // 2])) / 2,size // 2] 9         10     def findMedianSortedArrays(self, nums1, nums2):11         """12         :type nums1: List[int]13         :type nums2: List[int]14         :rtype: float15         """16         size1 = len(nums1)17         size2 = len(nums2)18         if size1 < size2:19             return self.findMedianSortedArrays(nums2,nums1)20         m1 = self.getMedian(nums1)21         m2 = self.getMedian(nums2)22         if size2 == 0:23             return m1[0]24         if size2 == 1:25             if size1 == 1:26                 return (float(nums1[0] + nums2[0])) / 227             if size1 % 2 == 0:28                 if nums2[0] < nums1[size1 //2 - 1]:29                     return nums1[size1 // 2 - 1]30                 if nums2[0] > nums1[size1 // 2 ]:31                     return nums1[size1 // 2]32                 else:33                     return nums2[0]34             else:35                 if nums2[0] < nums1[size1 // 2 - 1]:36                     return (float(nums1[size1 // 2 - 1] + nums1[size1 // 2])) / 237                 if nums2[0] > nums1[size1 // 2 + 1]:38                     return (float(nums1[size1 // 2] + nums1[size1 // 2 + 1])) / 239                 else:40                     return (float(nums2[0] + nums1[size1 // 2])) / 241         if size2 % 2 == 0:42             if size1 % 2 == 0:43                 if nums2[size2 // 2 - 1] < nums1[size1 //2 - 1] and nums2[size2 // 2] > nums1[size1 // 2]:44                     return m1[0]45                 if nums1[size1 // 2 - 1] < nums2[size2 // 2 - 1] and nums1[size1 // 2] > nums2[size2 // 2]:46                     return m2[0]47         if m1[0] < m2[0]:48             return self.findMedianSortedArrays(nums1[m2[1]:],nums2[:size2 - m2[1]])49         if m1[0] > m2[0]:50             return self.findMedianSortedArrays(nums1[:size1 - m2[1]],nums2[m2[1]:])51         else:52             return m1[0]