#4 Median of Two Sorted Arrays——Top 100 Liked Questions

绝地灬酷狼 2022-02-05 11:23 134阅读 0赞

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

You may assume **nums1** and **nums2** cannot be both empty.

**Example 1:**

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

**Example 2:**

nums1 = [1, 2]
    nums2 = [3, 4]

> """
> 
> 第一次：思路是将num2中的数据向num1中插，分三种情况：①有一个为空或者num2中的数据均小于num1中的数据；②num2中的数据均大于num1中的数据；③num1与num2中的数据有大有小。返回情况分两种：num1中的数据为偶数个，返回中间两个的平均数，num1中的数据为奇数个，返回中间一个数。
> 
> """
> 
> class Solution(object):  
>     def findMedianSortedArrays(self, nums1, nums2):  
>         """  
>         :type nums1: List\[int\]  
>         :type nums2: List\[int\]  
>         :rtype: float  
>         """  
>         m, n = len(nums1), len(nums2)  
>         x = m + n  
>         midden = \[x // 2, x // 2 -1\] if not x % 2 else \[x // 2\]     
>         if m == 0 or n == 0 or nums2\[n - 1\] <= nums1\[0\]:  
>             nums2.extend(nums1)  
>             nums1 = nums2  
>         elif nums2\[0\] >= nums1\[m - 1\]:  
>             nums1.extend(nums2)  
>         else:      
>             for num in nums2:  
>                 left = 0  
>                 right = len(nums1) - 1  
>                 while left < right:  
>                     mid = (left + right) // 2  
>                     if num < nums1\[mid\]:  
>                         if num > nums1\[mid - 1\]:  
>                             nums1.insert(mid, num)  
>                             break  
>                         else:  
>                             left, right = 0, mid - 1  
>                             continue  
>                     if num > nums1\[mid\]:  
>                         if num < nums1\[mid + 1\]:  
>                             nums1.insert(mid + 1, num)  
>                             break  
>                         else:  
>                             left, right = mid + 1, len(nums1) - 1  
>                             continue  
>                 if num <= nums1\[0\]:  
>                     nums1.insert(0, num)  
>                     continue
> 
>                 if num >= nums1\[-1\]:  
>                     nums1.append(num)  
>                     continue 
> 
>         return nums1\[midden\[0\]\] if len(midden) == 1 else (nums1\[midden\[0\]\] + nums1\[midden\[1\]\]) / 2.0
> 
>  """
> 
> Time Limit Exceeded
> 
> """

> """
> 
> 第二次：对nums1和nums2使用归并排序，排序结果保存到tmp中
> 
> """
> 
> class Solution(object):  
>     def findMedianSortedArrays(self, nums1, nums2):  
>         """  
>         :type nums1: List\[int\]  
>         :type nums2: List\[int\]  
>         :rtype: float  
>         """  
>         tmp = \[\]  
>         if len(nums1) == 0 or len(nums2) == 0 or nums1\[-1\] < nums2\[0\]:  
>             nums1.extend(nums2)  
>             tmp = nums1
> 
>         elif nums1\[0\] >  nums2\[-1\]:  
>             nums2.extend(nums1)  
>             tmp = nums2  
>         else:  
>             i, j = 0, 0  
>             while i < len(nums1) or j < len(nums2):  
>                 if i == len(nums1):   
>                     tmp.extend(nums2\[j:\])  
>                     break  
>                 elif j == len(nums2):   
>                     tmp.extend(nums1\[i:\])  
>                     break  
>                 else:  
>                     if nums1\[i\] < nums2\[j\]:  
>                         tmp.append(nums1\[i\])  
>                         i += 1  
>                     else:  
>                         tmp.append(nums2\[j\])  
>                         j += 1  
>         print(tmp)  
>         l = len(tmp)  
>         return tmp\[l//2\] if l % 2 else (tmp\[l//2\] + tmp\[(l//2)-1\]) / 2.0
> 
>  """
> 
> Runtime: 192 ms, faster than 7.41% of Python online submissions forMedian of Two Sorted Arrays.
> 
> Memory Usage: 12 MB, less than 5.48% of Python online submissions forMedian of Two Sorted Arrays.
> 
> """