【Python 千题 —— 算法篇】寻找两个正序数组的中位数

Python 千题持续更新中 ……

脑图地址 👉：⭐https://twilight-fanyi.gitee.io/mind-map/Python千题.html⭐

题目背景

在处理大规模数据时，我们经常需要对数据进行排序和分析。一个常见问题是如何高效地从两个正序数组中找出它们的中位数。该问题不仅是算法面试中的经典题目之一，还在数据分析、统计学等多个领域有实际应用。

求解两个正序数组的中位数是一种复杂的计算，因为它要求我们在保证时间复杂度足够低的情况下，不破坏正序数组的性质。理解和解决这个问题，可以大幅提升我们在算法设计与优化上的能力。

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，要求算法的时间复杂度为 O(log(m+n))。

你需要实现一个函数 findMedianSortedArrays()，该函数接收两个正序数组 nums1 和 nums2 作为输入，并返回它们的中位数。

输入描述

• 两个正序数组 nums1 和 nums2，每个数组的长度在 [0, 1000] 之间，且元素是有序的整数。

输出描述

• 一个浮点数，表示两个数组合并后的中位数，结果需要保留到小数点后 1 位。

示例

示例 ①

输入：

# 调用 findMedianSortedArrays() 函数
print(findMedianSortedArrays([1, 3], [2]))

输出：

2.0

解释：合并数组 [1, 2, 3]，中位数是 2。

示例 ②

输入：

print(findMedianSortedArrays([1, 2], [3, 4]))

输出：

2.5

解释：合并数组 [1, 2, 3, 4]，中位数是 (2 + 3) / 2 = 2.5。

---

代码讲解与多种解法

解法一：合并排序法

一种直观的解法是将两个数组合并为一个，然后对合并后的数组进行排序。排序后，根据数组长度的奇偶性判断并找到中位数。这种方法虽然易于理解，但时间复杂度为 O((m + n)log(m + n))，在效率上不够理想。

def findMedianSortedArrays(nums1, nums2):merged = sorted(nums1 + nums2)n = len(merged)if n % 2 == 1:return merged[n // 2]else:return (merged[n // 2 - 1] + merged[n // 2]) / 2

优点：

• 思路清晰，容易实现。

缺点：

• 时间复杂度较高 O((m + n)log(m + n))，尤其在数据规模较大的情况下效率较低。

解法二：双指针法

双指针法通过利用两个数组已经排序的特点，不需要完整合并数组，而是使用双指针遍历两个数组，逐步找到中位数位置。这种方法的时间复杂度为 O(m + n)，比合并排序法有所改进，但不符合 O(log(m + n)) 的要求。

def findMedianSortedArrays(nums1, nums2):m, n = len(nums1), len(nums2)merged = []i, j = 0, 0while i < m and j < n:if nums1[i] < nums2[j]:merged.append(nums1[i])i += 1else:merged.append(nums2[j])j += 1merged += nums1[i:] + nums2[j:]total_len = m + nif total_len % 2 == 1:return merged[total_len // 2]else:return (merged[total_len // 2 - 1] + merged[total_len // 2]) / 2

优点：

• 时间复杂度降为 O(m + n)，相较于合并排序法更加高效。

缺点：

• 时间复杂度仍然不满足 O(log(m + n)) 的要求。

解法三：二分查找法

为了满足时间复杂度 O(log(m + n)) 的要求，我们可以采用二分查找的方法。在两个数组中使用二分查找法寻找中位数，核心思想是通过划分两个数组，使得左半部分的所有元素都小于右半部分的所有元素。

我们可以通过在较短的数组中使用二分查找，不断调整两个数组的划分位置，直到找到合适的中位数。

def findMedianSortedArrays(nums1, nums2):if len(nums1) > len(nums2):nums1, nums2 = nums2, nums1m, n = len(nums1), len(nums2)imin, imax, half_len = 0, m, (m + n + 1) // 2while imin <= imax:i = (imin + imax) // 2j = half_len - iif i < m and nums1[i] < nums2[j - 1]:imin = i + 1elif i > 0 and nums1[i - 1] > nums2[j]:imax = 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:return max_of_leftif 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

优点：

• 时间复杂度为 O(log(min(m, n)))，效率非常高。
• 只需在较短的数组上进行二分查找，避免了不必要的计算。

缺点：

• 实现起来稍微复杂一些，需要对二分查找和数组的划分有深入理解。

---

总结与思考

在处理寻找两个正序数组中位数的问题时，使用不同的方法可以得到不同的效率：

1. 合并排序法：易于理解，但时间复杂度较高，适合小规模数据。
2. 双指针法：通过双指针合并数组，时间复杂度 O(m + n)，适合中等规模数据。
3. 二分查找法：通过二分查找，在较短数组上进行划分，时间复杂度为 O(log(min(m, n)))，是处理大规模数据的最佳选择。

对于这种涉及高效搜索和排序的题目，掌握二分查找的应用至关重要。通过本题目，我们不仅能够提升对数组和中位数的理解，还能够学到如何优化时间复杂度，使算法在处理大规模数据时更加高效。

---

扩展思考

1. 统计学应用：中位数在统计分析中起着重要作用，掌握高效的中位数计算方法可以帮助我们在大数据处理中更快得出结论。
2. 二分查找应用：本题目中的二分查找方法，不仅适用于数组合并中位数问题，还可以拓展到其他查找问题中，比如查找区间、寻找特定元素等。
3. 复杂数据结构的处理：在实际应用中，数据可能并非简单的正序数组，而是树、图等复杂数据结构，学会如何在这些结构中寻找中位数同样是算法设计的重要内容。

希望通过本文的讲解，你能够深入理解寻找两个正序数组中位数的各种方法，并掌握高效的算法技巧。

持续关注博客，获取更多编程练习与技巧！

作者信息 作者 ： 繁依Fanyi CSDN： https://techfanyi.blog.csdn.net 掘金：https://juejin.cn/user/4154386571867191