4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

难度: Hard

刷题内容

原题连接

内容描述

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]

The median is (2 + 3)/2 = 2.5

解题方案

思路 1
*- 时间复杂度: O((m+n) * lg(m+n))- 空间复杂度: O(m+n)*

首先最简单粗暴的方法,就是我们将两个数字列表合并起来,排好序,找到中间的median就ok了,但是千万要注意一点,如果median有两个,需要算平均

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = sorted(nums1 + nums2) 
        if len(nums) % 2 == 1:
            return nums[len(nums)//2]
        else:
            return (nums[len(nums)//2-1] + nums[len(nums)//2]) / 2.0

思路 2
- 时间复杂度: O(lg(m+n))- 空间复杂度: O(1)

这时候我们观察到题目给的一个条件,nums1nums2本身也是有序的,放着这个条件不用反而用思路一是不是有点浪费了?换句话说我们没必要把他们整个排序,于是我们可以把它转化成经典的 findKth问题

首先转成求AB数组中第k小的数的问题, 然后用k//2AB中分别找。

比如 k = 6, 分别看AB中的第3个数, 已知 A1 <= A2 <= A3 <= A4 <= A5...B1 <= B2 <= B3 <= B4 <= B5..., 如果A3 <= B3, 那么第6小的数肯定不会是A1, A2, A3, 因为最多有两个数小于A1(B1, B2), 三个数小于A2(A1, B1, B2), 四个数小于A3(A1, A2, B1, B2)。 关键点是从k//2 开始来找。那就可以排除掉A1, A2, A3, 转成求A4, A5, ... B1, B2, B3, ...这些数中第3小的数的问题, k就被减半了。

k == 1或某一个数组空了, 这两种情况都是终止条件。

beats 64.27%

```python
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
def findKth(A, B, k):
if len(A) == 0: # A 为空,第 k 小的数就是 B 中第k个数
return B[k-1]
if len(B) == 0: # B 为空,第 k 小的数就是 A 中第k个数
return A[k-1]
if k == 1: # k 为 1 就是求最小的数
return min(A[0], B[0])

top Created with Sketch.