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

本文主要是介绍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

这篇关于python 寻找两个正序数组的中位数(leetcode)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！