leetcode代码记录(寻找两个正序数组的中位数

简介: leetcode代码记录(寻找两个正序数组的中位数

1. 题目:

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

算法的时间复杂度应该为 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

2. 我的代码:

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 快慢指针
        p_1 = 0
        p_2 = 0

        new_nums = []

        # 合并数组
        p = 0
        while p_1 < len(nums1) and p_2 < len(nums2):
            if nums1[p_1] < nums2[p_2]:
                new_nums.append(nums1[p_1])
                p_1 += 1
            else:
                new_nums.append(nums2[p_2])
                p_2 += 1
            
        if p_1 < len(nums1):
            new_nums += nums1[p_1:]
        if p_2 < len(nums2):
            new_nums += nums2[p_2:]

        # 找中位数
        if len(new_nums) % 2 == 0:
            return (new_nums[len(new_nums) // 2] + new_nums[len(new_nums) // 2 - 1]) / 2
        else:
            return new_nums[len(new_nums) // 2]

利用快慢指针,求解两个有序数组的并集(并集仍然保持有序),两个指针分别从num1和num2左边向右移动,将更小的元素添加到新数组中。

左右指针走完之后,将剩余的元素直接添加到末尾即可。

中位数计算就是奇数偶数的区别了,比较好理解。

目录
相关文章
|
18小时前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
18小时前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
2天前
力扣-2029-石子游戏-‘屎山’代码
力扣-2029-石子游戏-‘屎山’代码
11 3
|
4天前
|
存储 算法 数据可视化
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
|
4天前
|
存储 算法 数据可视化
|
4天前
|
存储 传感器 算法
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
|
4天前
|
存储 算法 数据挖掘
LeetCode 题目 81:搜索旋转排序数组 II
LeetCode 题目 81:搜索旋转排序数组 II
|
4天前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
4天前
|
存储 SQL 算法
LeetCode第53题:最大子数组和【python 5种算法】
LeetCode第53题:最大子数组和【python 5种算法】
|
4天前
|
存储 算法 数据挖掘
LeetCode第33题:搜索旋转排序数组【python】
LeetCode第33题:搜索旋转排序数组【python】