力扣(leetcode)第4题寻找两个正序数组的中位数(Python)

2023-12-24 23:03:13

4.寻找两个正序数组的中位数

题目链接:4.寻找两个正序数组的中位数

给定两个大小分别为 m m m n n n 的正序(从小到大)数组 n u m s 1 nums1 nums1 n u m s 2 nums2 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O ( l o g ( m + n ) ) O(log (m+n)) O(log(m+n))

示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

提示:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

解答一

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = nums1 + nums2
        n = sorted(nums)
        m = len(n)
        if m%2 == 0:
            return (n[m//2]+n[m//2-1])/2
        else:
            return n[m//2]

解答二

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        if m == 0:
            return self.middle(nums2)
        if n == 0:
            return self.middle(nums1)
        i,j,k = 0,0,0
        res = []
        while i<m and j<n:
            if nums1[i]<nums2[j]:
                res.append(nums1[i])
                i += 1
            elif nums1[i]>nums2[j]:
                res.append(nums2[j])
                j += 1
            else:
                res.append(nums1[i])
                res.append(nums2[j])
                i += 1
                j += 1
        while i<m:
            res.append(nums1[i])
            i += 1
        while j<n:
            res.append(nums2[j])
            j += 1
        return self.middle(res)
    def middle(self,num):
        n = len(num)
        if n%2 == 0:
            return (num[n//2]+num[n//2-1]) /2
        else:
            return num[n//2]*1.0

最后,我写了一篇MySQL教程,里面详细的介绍了MySQL的基本概念以及操作指令等内容,欢迎阅读!
MySQL数据库万字保姆级教程

文章来源:https://blog.csdn.net/qq_58737789/article/details/135186396
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。