当前位置：首页 > article >正文

LeetCode【0004】寻找两个正序数组的中位数

article 2024/11/13 17:15:16

本文目录

1 中文题目
2 求解思路
- 2.1 基础解法：合并排序法
- 2.2 优化解法：双指针
- 2.3 最优解法：二分查找
3 题目总结

1 中文题目

给定两个大小分别为 $m$ 和 $n$ 的正序（从小到大）数组 $n u m s 1$ 和 $n u m s 2$ 。请你找出并返回这两个正序数组的中位数。并且算法的时间复杂度应该为 $O (l o g (m + n))$ 。

示例 1：

输入： $n u m s 1 = [1, 3], n u m s 2 = [2]$
输出： $2.00000$
解释：合并数组 = $[1, 2, 3]$ ，中位数 $2$

示例 2：

输入： $n u m s 1 = [1, 2], n u m s 2 = [3, 4]$
输出： $2.50000$
解释：合并数组 = $[1, 2, 3, 4]$ ，中位数 $(2 + 3) /2 = 2.5$

提示：

$\leq nums1.length \leq 1000$
$0\leq nums2.length \leq 1000$
$\leq m + n \leq 2000$
$-10^6 \leq nums1[i], nums2[i] \leq 10^6$

2 求解思路

2.1 基础解法：合并排序法

思路
将两个有序数组合并成一个有序数组，根据合并后数组的长度判断中位数位置，计算并返回中位数

a. 初始化阶段

创建空数组 $m er g e d$ 用于存储合并结果
初始化两个指针 $i$ 和 $j$ 分别指向 $n u m s 1$ 和 $n u m s 2$ 的起始位置

b. 合并阶段

比较 $n u m s 1 [i]$ 和 $n u m s 2 [j]$ 的大小
将较小的元素加入 $m er g e d$ 数组
移动对应的指针
重复直到某个数组遍历完成

c. 处理剩余元素

将未遍历完的数组剩余元素直接加入 $m er g e d$

d. 计算中位数

判断总长度的奇偶性
偶数长度：返回中间两个数的平均值
奇数长度：返回中间的数

Python代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        """
        寻找两个正序数组的中位数
        
        参数:
            nums1: 第一个有序数组
            nums2: 第二个有序数组
            
        返回:
            float: 两个数组合并后的中位数
        """
        # 用于存储合并后的有序数组
        merged = []
        
        # 初始化两个数组的指针
        i, j = 0, 0
        m, n = len(nums1), len(nums2)
        
        # 同时遍历两个数组，比较并合并
        while i < m and j < n:
            if nums1[i] <= nums2[j]:
                # nums1中的元素更小，将其加入merged
                merged.append(nums1[i])
                i += 1
            else:
                # nums2中的元素更小，将其加入merged
                merged.append(nums2[j])
                j += 1
        
        # 处理剩余元素
        # 如果nums1还有剩余元素
        while i < m:
            merged.append(nums1[i])
            i += 1
        
        # 如果nums2还有剩余元素
        while j < n:
            merged.append(nums2[j])
            j += 1
        
        # 计算合并后数组的总长度
        total_length = m + n
        
        # 判断总长度的奇偶性并计算中位数
        if total_length % 2 == 0:
            # 偶数长度：取中间两个数的平均值
            return (merged[total_length//2-1] + merged[total_length//2]) / 2
        else:
            # 奇数长度：直接返回中间的数
            return merged[total_length//2]

时空复杂度分析

时间复杂度： $O (m + n)$
- 合并两个数组需要 $O (m + n)$ 时间
- 访问中位数位置需要 $O (1)$ 时间
空间复杂度： $O (m + n)$

2.2 优化解法：双指针

思路
不需要真正合并数组，只需遍历到中位数位置，使用两个指针交替前进，维护当前值和前一个值

a. 初始化

计算总长度和需要遍历的次数
设置双指针指向两个数组起始位置

b. 遍历过程

比较两个指针指向的值
选择较小值前进
处理数组遍历完的边界情况

c. 结果计算

奇数长度：返回当前值
偶数长度：计算中间两个数的平均值

python代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        """
        使用双指针法查找两个有序数组的中位数
        
        算法思路：
        1. 使用两个指针分别遍历两个数组
        2. 按顺序合并两个数组的元素，直到达到中位数位置
        3. 根据总长度的奇偶性返回中位数
        
        参数:
            nums1: 第一个有序数组
            nums2: 第二个有序数组
        返回:
            float: 两个数组合并后的中位数
        """
        # 获取两个数组的长度
        m, n = len(nums1), len(nums2)
        total_length = m + n
        
        # 计算需要遍历的次数
        # 如果总长度为奇数，需要遍历到中间位置
        # 如果总长度为偶数，需要遍历到中间两个数
        k = (total_length + 1) // 2
        
        # 定义双指针，分别指向两个数组的起始位置
        p1 = p2 = 0
        
        # 记录当前值和前一个值
        # 用于计算偶数长度时的平均值
        current = previous = 0
        
        # 遍历直到达到中位数位置
        for _ in range(k):
            # 保存前一个值
            previous = current
            
            # 处理边界情况和比较大小
            if p1 == m:  # nums1已经遍历完
                current = nums2[p2]
                p2 += 1
            elif p2 == n:  # nums2已经遍历完
                current = nums1[p1]
                p1 += 1
            elif nums1[p1] <= nums2[p2]:  # nums1当前值更小
                current = nums1[p1]
                p1 += 1
            else:  # nums2当前值更小
                current = nums2[p2]
                p2 += 1
        
        # 根据总长度的奇偶性返回结果
        if total_length % 2 == 1:
            # 奇数长度：直接返回中间值
            return current
        else:
            # 偶数长度：返回中间两个数的平均值
            # 如果当前遍历次数不够，需要再取一个数
            if p1 == m:  # nums1已经遍历完
                next_value = nums2[p2]
            elif p2 == n:  # nums2已经遍历完
                next_value = nums1[p1]
            else:  # 比较两个数组当前值
                next_value = min(nums1[p1], nums2[p2])
            
            return (current + next_value) / 2

时空复杂度分析

时间复杂度： $O (m + n)$
- 最多遍历到中位数位置： $(m + n) /2$
- 每次遍历常数操作
- 双指针移动次数： $O ((m + n) /2)$
空间复杂度： $O (1)$
- 双指针：2个整数
- 当前值和前一个值：2个整数
- 其他临时变量：常数个
- 不需要额外数组

2.3 最优解法：二分查找

思路

分割点：将两个数组各自分成左右两部分
平衡条件：左半部分长度等于右半部分（或多1）
正确性条件：左半部分最大值 ≤ 右半部分最小值

查找过程：
（1）在较短数组中二分查找分割点
（2）根据总长度确定另一个数组的分割点
（3）判断分割是否满足条件
（4）调整分割点位置直到找到答案

python代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        """
        使用分治法查找两个有序数组的中位数
        
        核心思想：
        1. 将数组分成左右两部分，使得左部分的长度等于右部分
        2. 保证左部分的最大值小于等于右部分的最小值
        3. 通过二分查找确定分割点
        
        参数:
            nums1: 第一个有序数组
            nums2: 第二个有序数组
        返回:
            float: 两个数组合并后的中位数
        """
        # 确保 nums1 是较短的数组，优化查找过程
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        
        m, n = len(nums1), len(nums2)
        
        # 特殊情况处理：空数组
        if m == 0:
            if n % 2 == 0:
                return (nums2[n//2 - 1] + nums2[n//2]) / 2
            return nums2[n//2]
            
        # 初始化二分查找的范围
        # left和right表示nums1可能的分割位置
        left, right = 0, m
        
        while left <= right:
            # 在nums1中找分割点
            i = (left + right) // 2
            # nums2的分割点由nums1的分割点决定
            # 确保左右两部分长度相等或左部分多一个
            j = (m + n + 1) // 2 - i
            
            # 获取分割点左右的值
            # 使用无穷大和无穷小处理边界情况
            nums1_left = float('-inf') if i == 0 else nums1[i-1]
            nums1_right = float('inf') if i == m else nums1[i]
            nums2_left = float('-inf') if j == 0 else nums2[j-1]
            nums2_right = float('inf') if j == n else nums2[j]
            
            # 判断分割是否合适
            if nums1_left <= nums2_right and nums2_left <= nums1_right:
                # 找到合适的分割点
                # 根据总长度的奇偶性返回结果
                if (m + n) % 2 == 0:
                    # 偶数个元素：返回左半部分最大值和右半部分最小值的平均值
                    left_max = max(nums1_left, nums2_left)
                    right_min = min(nums1_right, nums2_right)
                    return (left_max + right_min) / 2
                else:
                    # 奇数个元素：返回左半部分的最大值
                    return max(nums1_left, nums2_left)
            elif nums1_left > nums2_right:
                # nums1的分割点太靠右，需要向左移动
                right = i - 1
            else:
                # nums1的分割点太靠左，需要向右移动
                left = i + 1

时空复杂度分析

时间复杂度分析： $O (l o g (min (m, n)))$
二分查找分析：在较短数组中进行二分查找，每次迭代减少一半搜索空间，迭代次数取决于较短数组长度。具体分析：
- 初始范围： $[0, m] ， m$ 为较短数组长度
- 每次迭代：范围减半
- 迭代次数： $l o g (m)$
- 每次迭代操作： $O (1)$
空间复杂度分析： $O (1)$