4. Median of Two Sorted Arrays

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

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

## 解题方案

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

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

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

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