给定两个大小分别为m和n 的正序(从小到大)数组nums1 和nums2.请你找出并返回这两个正序数组的中位数。
算法是时间复杂度应该为o(log(m*n))
- 解法一
- 使用python 的库函数解决
class Solution1:
def findMedianSortedArrays(self, nums1, nums2) -> float:
nums1.extend(nums2)
length = len(nums1)
nums1.sort()
return nums1[length//2] if length ^ 1 < length else (nums1[length//2] + nums1[length//2-1])/2
- 解法二
- 拼接起来,利用题目给的有序性,然后在找到中位数。
- 代码如下:
class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:
l1 = len(nums1)
l2 = len(nums2)
stack = []
index2 = 0
index1 = 0
while index1 < l1 and index2 < l2:
while index1 < l1 and nums1[index1] <= nums2[index2]:
stack.append(nums1[index1])
index1 += 1
if index1 >= l1:
break
while index2 < l2 and nums1[index1] > nums2[index2] :
stack.append(nums2[index2])
index2 += 1
if index1 >= l1:
stack = stack + nums2[index2:]
else:
stack = stack + nums1[index1:]
length=len(stack)
return stack[length//2] if length ^ 1 < length else (stack[length//2] + stack[length//2-1])/2