LeetCode刷题：寻找两个正序数组的中位数【4/1000 第四题】【python + go】

news/2024/7/27 8:55:31/文章来源:https://blog.csdn.net/CCIEHL/article/details/137253819

👤作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
作者专栏每日更新：
LeetCode解锁1000题:打怪升级之旅
python数据分析可视化:企业实战案例
备注说明：方便大家阅读，统一使用python，带必要注释，公众号数据分析螺丝钉一起打怪升级

题库中的“寻找两个正序数组的中位数”问题是一个经典的算法挑战。这个问题不仅出现在在线编程平台上，也是许多技术面试中的常见题目，值得深入探讨一下

问题描述

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

输入：nums1 = [1,3], nums2 = [2]
输出：2.0
解释：合并数组 = [1,2,3]，中位数 2

解题思路

理解这个问题的关键在于，两个数组是有序的，这为我们提供了很多可以利用的性质。一种直观的解法是将两个数组合并成一个大的有序数组，然后直接找到中位数。虽然这种方法很直接，但它的时间复杂度为 (O(m+n))，并不是最优解。

最优解法 —— 二分查找法

要提高效率，可以考虑二分查找法。核心思路是，中位数将一个集合分为两个长度相等的子集，一个子集中的所有元素都小于另一个子集中的元素。对于两个有序数组，我们可以利用二分查找在 (O(\log(m+n))) 的时间复杂度内找到中位数。

算法步骤

确定较短的数组：为了减少查找的范围，我们总是在两个数组中较短的那个进行二分查找。
二分查找:在较短数组中进行二分查找，确定一个切点，使得两个数组被分为左右两个部分，左边部分的元素总数等于右边部分（或者多一个，如果总元素数为奇数）。
调整切点:通过比较两个数组在切点附近的元素，调整切点的位置，直到满足中位数的性质：左边部分的最大元素小于或等于右边部分的最小元素。
计算中位数:根据切点确定的左右两部分，计算中位数。

python示例

def find_median_sorted_arrays(nums1: [int], nums2: [int]) -> float:# 确保 nums1 是两个中较短的数组if len(nums1) > len(nums2):nums1, nums2 = nums2, nums1m, n = len(nums1), len(nums2)# 初始化二分查找的边界left, right, half_len = 0, m, (m + n + 1) // 2while left <= right:# i 和 j 分别为两个数组的切分点i = (left + right) // 2j = half_len - i# 调整左边界if i < m and nums2[j-1] > nums1[i]:left = i + 1# 调整右边界elif i > 0 and nums1[i-1] > nums2[j]:right = i - 1else:# 找到合适的切分点，计算中位数if i == 0: max_of_left = nums2[j-1]elif j == 0: max_of_left = nums1[i-1]else: max_of_left = max(nums1[i-1], nums2[j-1])if (m + n) % 2 == 1:# 如果 m + n 是奇数，中位数是左半部的最大值return max_of_left# 如果 m + n 是偶数，中位数是左半部的最大值和右半部的最小值的平均值if i == m: min_of_right = nums2[j]elif j == n: min_of_right = nums1[i]else: min_of_right = min(nums1[i], nums2[j])return (max_of_left + min_of_right) / 2.0return 0# 示例测试
nums1 = [1, 3]
nums2 = [2]
print(f"中位数是：{find_median_sorted_arrays(nums1, nums2)}")

代码解读：

让我们一步一步分析上面的Python代码，以解释它是如何找到两个有序数组中位数的。

关键变量

nums1 和 nums2: 输入的两个有序数组。
m 和 n: 分别是 nums1 和 nums2 的长度。
left 和 right:用于在较短数组 nums1 上执行二分查找的指针。
half_len: 两个数组合并后左半部分的长度。

二分查找

二分查找的目的是在较短的数组 nums1 中找到一个位置 i，同时在 nums2 中找到位置 j，使得：

nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[I]

位置 i 和 j 的选取使得nums1和nums2被分割成两个部分，左半部分的所有元素都不大于右半部分的元素。

边界条件处理

循环中的条件判断用于处理边界条件，确保不会访问数组外的元素：

如果 i 还可以增大，并且 nums2[j-1] > nums1[i]，那么需要将 left 移动到 i + 1，这意味着 i 的位置太小，需要向右移动以增大 i。
如果 i 还可以减小，并且 nums1[i-1] > nums2[j]，那么需要将 right 移动到 i - 1，这意味着 i 的位置太大，需要向左移动以减小 i。

计算中位数

一旦找到了合适的 i 和 j，中位数可以通过下列方式计算：

当 m + n 为奇数时，中位数是左半部分的最大值。
当 m + n 为偶数时，中位数是左半部分的最大值和右半部分的最小值的平均值。
代码中使用了几个条件判断来处理这个逻辑，确保即使在边界条件下（比如某一数组的所有元素都在另一数组的左边或右边时）也能正确计算中位数。

返回结果

最后，根据 m + n 的奇偶性，返回合适的中位数值。

这个算法精妙地利用了二分查找和有序数组的性质来高效地解决问题，避免了将两个数组合并后再查找中位数，从而达到了更优的时间复杂度 O(log(min(m,n)))。

goland示例

我们同样可以采用二分查找法。以下是 Go 语言版本的实现及其解读。

package mainimport ("fmt""math"
)func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {// 确保 nums1 是较短的数组if len(nums1) > len(nums2) {nums1, nums2 = nums2, nums1}m, n := len(nums1), len(nums2)left, right, halfLen := 0, m, (m+n+1)/2var maxOfLeft, minOfRight intfor left <= right {i := (left + right) / 2j := halfLen - iif i < m && nums2[j-1] > nums1[i] {left = i + 1} else if i > 0 && nums1[i-1] > nums2[j] {right = i - 1} else {if i == 0 {maxOfLeft = nums2[j-1]} else if j == 0 {maxOfLeft = nums1[i-1]} else {maxOfLeft = int(math.Max(float64(nums1[i-1]), float64(nums2[j-1])))}if (m+n)%2 == 1 {return float64(maxOfLeft)}if i == m {minOfRight = nums2[j]} else if j == n {minOfRight = nums1[i]} else {minOfRight = int(math.Min(float64(nums1[i]), float64(nums2[j])))}return float64(maxOfLeft+minOfRight) / 2.0}}return 0.0
}func main() {nums1 := []int{1, 3}nums2 := []int{2}fmt.Println("中位数是：", findMedianSortedArrays(nums1, nums2))
}

代码解读

此解决方案首先检查 nums1 和 nums2 的长度，确保 nums1 是较短的数组，这样可以减少我们二分查找的范围。
left 和 right 变量定义了 nums1 上的查找范围，而 halfLen 变量则根据两数组的总长度计算中位数左侧的元素数量。
在二分查找过程中，i 和 j 分别表示 nums1 和 nums2 中用于分割数组的索引。left 和 right 的调整基于 nums1[i] 和 nums2[j] 的比较，以确保左侧的最大值不大于右侧的最小值。
当找到合适的分割线时，根据奇偶性计算中位数。如果总长度是奇数，则中位数是左侧的最大值；如果是偶数，则中位数是左侧最大值和右侧最小值的平均数。