欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Daily coding:寻找两个正序数组的中位数

程序员文章站 2022-05-28 14:47:10
...

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。

请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

 代码1:

class Solution:
    def findMedianSortedArrays(self, nums1, nums2) -> float:
        # 1. 下面这些情况进行处理
        len1 = len(nums1)
        len2 = len(nums2)
        # 一个数组为空,补上另一个数组,中值/2后还是原来的结果(类似于: 3 * 2 / 2还是原来的结果)
        if len1 == 0: nums1 = nums2
        elif len2 == 0: nums2 = nums1
        if len1 == 1 and len2 == 1: return (nums1[0] + nums2[0]) / 2 # 这个情况直接返回

        # 2. 获取基本变量信息
        lenAll = len1 + len2
        mid = int(lenAll / 2 + 1) # 使运行到这里长度总>=3,mid中值的位置(3/2+1=2、4/2+1=3)
        i = j = 0 # 便利索引
        ary = [0, 0] # 存储中值的列表

        # 3. 核心代码
        while i < len1 and j < len2:
            # 假定两个数字长度相同,和一个数组遍历到临界点的时候,刚好i + j == mid

            if nums1[i] < nums2[j]:
                ary[(i + j) % 2] = nums1[i]
                i += 1
            else:
                ary[(i + j) % 2] = nums2[j]
                j += 1
            if i + j == mid: break # 达到中值 退出循环
        # 对两个数组长度不一,以及一个数组下标i或j先行达临界点(nums1.length = i或nums2.length == j)进行补充
        while i + j < mid and i == len1:
            ary[(i + j) % 2] = nums2[j]
            j += 1
        while i + j < mid and j == len2:
            ary[(i + j) % 2] = nums1[i]
            i += 1

        # 4. 判断后返回对应的运行结果
        if lenAll % 2 != 0:
            return ary[(i + j - 1) % 2] # 总长度为奇数,最后一个赋值就是中值。
        else:
            return (ary[0] + ary[1]) / 2 # 总长度为偶数,直接返回他们相加的平均值。

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/shu-zu-cun-chu-fa-jian-dan-yi-li-jie-on-by-guai-ma/

代码2:

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1.extend(nums2)
        nums1.sort()
        length=len(nums1)
        if length%2==1:
            return nums1[length//2]
        else:
            return (nums1[length//2]+nums1[length//2-1])/2
         

算法的时间复杂度和空间复杂度

相关标签: python每日一练