python 寻找两个正序数组的中位数(leetcode)

给定两个大小分别为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

上一篇:自己编程实现fft


下一篇:如何求出天干地支