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

今日打卡，Leetcode第四题：寻找两个正序数组的中位数，博主表示就会sorted

news 2025/5/29 10:14:02

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

博主只会第一个暴力解法，然后将官网上的源码上添加些注释，尝试理解，分下今日刷题记录

题目描述

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

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

解法一：暴力合并法（不符合题目要求的时间复杂度）

这种方法最为直观，但时间复杂度为 O((m+n)log(m+n))，不符合题目要求。

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:nums = sorted(nums1 + nums2)  # 合并并排序两个数组n = len(nums)result = 0for i in range(n):result += nums[i]return result / n  # 这里实际上计算的是平均值而非中位数，正确的中位数计算应为：# 如果n为奇数，返回nums[n//2]# 如果n为偶数，返回(nums[n//2-1] + nums[n//2])/2

注意：上述代码中计算的是平均值而非中位数。正确的中位数计算应该是：
if n % 2 == 1:return nums[n//2]
else:return (nums[n//2-1] + nums[n//2]) / 2

解法二：二分查找法（符合题目要求的时间复杂度）

这种方法的核心思想是将"寻找中位数"转化为"寻找第k小的元素"的问题。

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:def getKthElement(k):"""- 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较- 这里的 "/" 表示整除- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个- 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个- 这样 pivot 本身最大也只能是第 k-1 小的元素- 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组- 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组- 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数"""index1, index2 = 0, 0  # 初始化两个数组的起始索引while True:# 特殊情况处理if index1 == m:  # m是数组num1的长度，如果nums1已经全部被排除return nums2[index2 + k - 1]  # 直接返回nums2中的第k个元素if index2 == n:  #n是数组num2的长度 如果nums2已经全部被排除return nums1[index1 + k - 1]  # 直接返回nums1中的第k个元素if k == 1:  # 如果要找第1小的元素return min(nums1[index1], nums2[index2])  # 返回两个数组当前位置的最小值# 正常情况处理newIndex1 = min(index1 + k // 2 - 1, m - 1)  # 计算nums1中的比较位置，防止越界newIndex2 = min(index2 + k // 2 - 1, n - 1)  # 计算nums2中的比较位置，防止越界pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]  # 取出比较值# 比较两个数组的元素，排除较小元素所在的部分if pivot1 <= pivot2:  # 如果nums1的元素较小k -= newIndex1 - index1 + 1  # 更新k值，减去排除的元素个数index1 = newIndex1 + 1  # 更新nums1的起始位置else:  # 如果nums2的元素较小k -= newIndex2 - index2 + 1  # 更新k值，减去排除的元素个数index2 = newIndex2 + 1  # 更新nums2的起始位置m, n = len(nums1), len(nums2)  # 获取两个数组的长度totalLength = m + n  # 计算总长度# 根据总长度的奇偶性，计算中位数if totalLength % 2 == 1:  # 如果总长度为奇数return getKthElement((totalLength + 1) // 2)  # 返回中间的元素else:  # 如果总长度为偶数return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2  # 返回中间两个元素的平均值

详细解释

二分查找法的核心思想

问题转化：中位数可以转化为找第k小的元素
- 如果总长度为奇数，中位数是第(m+n+1)/2小的元素
- 如果总长度为偶数，中位数是第(m+n)/2小和第(m+n)/2+1小的元素的平均值
二分排除法：每次比较两个数组中第k/2个元素，排除较小值所在数组的前k/2个元素

算法流程图解

假设有两个数组：

nums1 = [1, 3, 5, 7, 9]
nums2 = [2, 4, 6, 8, 10]

要找这两个数组合并后的中位数：

总长度为10，是偶数，需要找第5小和第6小的元素的平均值
寻找第5小的元素：
- 比较nums1[5/2-1]=nums1[1]=3和nums2[5/2-1]=nums2[1]=4
- 3<4，排除nums1的[1,3]，k=3，nums1现在从索引2开始
- 比较nums1[3/2-1+2]=nums1[3]=7和nums2[3/2-1]=nums2[0]=2
- 7>2，排除nums2的[2]，k=2，nums2现在从索引1开始
- 比较nums1[2/2-1+2]=nums1[2]=5和nums2[2/2-1+1]=nums2[1]=4
- 5>4，排除nums2的[4]，k=1，nums2现在从索引2开始
- k=1，返回min(nums1[2], nums2[2])=min(5,6)=5
寻找第6小的元素（类似过程）：结果为6
中位数=(5+6)/2=5.5