两个排序数组的中位数——LeetCode高难度解题方案
内容提要
中位数是统计学中的中间值，代表性强。LeetCode的第4个难题是找到两个排序数组的中位数，要求时间和空间复杂度优化。一种方法是合并和排序数组，但效率低。另一种优化的方法是利用二分查找，时间复杂度为O(log(min(m,n)))，空间复杂度为O(1)。
延伸解读
暴力解法的效率瓶颈
合并两个有序数组再排序的时间复杂度为O((m+n) log(m+n))，空间复杂度为O(m+n)。这种方法没有利用数组已排序的特性，当输入规模较大时性能较差。题目约束中m+n最大为2000，暴力解法虽可通过，但并非最优，且不符合题目对时间复杂度的进阶要求。
二分查找优化的核心思路
优化解法通过二分查找在较短数组上确定分区点，将两个数组逻辑上分为左右两半，使得左半部分的最大值不大于右半部分的最小值。这样中位数只依赖于分区边界元素，无需合并数组。时间复杂度降至O(log(min(m,n)))，空间复杂度为O(1)，显著优于暴力解法。
实现中的关键细节
代码首先确保nums1是较短的数组，以缩小二分范围。分区点计算后，需处理边界情况：当分区点位于数组端点时，将左侧最大值设为负无穷、右侧最小值设为正无穷。根据maxLeftX与minRightY等比较结果调整二分边界，直到满足交叉条件。最终根据总长度奇偶性返回中位数。
Q&A
什么是中位数，它在统计学中有什么意义？
中位数是统计学中的中间值，具有代表性，能够反映数据的中心趋势。
LeetCode的第4个难题是什么？
LeetCode的第4个难题是找到两个排序数组的中位数，要求优化时间和空间复杂度。
合并和排序数组的方法有什么缺点？
合并和排序数组的方法效率低，时间复杂度为O((m+n) log(m+n))，空间复杂度为O(m+n)，不适合大输入。
如何利用二分查找找到两个排序数组的中位数？
通过将数组分成两半，计算分区点，并比较分区点的元素来调整分区，直到找到中位数。
优化方法的时间和空间复杂度是多少？
优化方法的时间复杂度为O(log(min(m,n)))，空间复杂度为O(1)。
在优化方法中，如何确保第一个数组是较小的数组？
在优化方法中，首先检查两个数组的长度，如果第一个数组较大，则交换两个数组。
