【LeetCode 热题 100】4. 寻找两个正序数组的中位数——（解法一）线性扫描
Problem: 4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(M + N)
- 空间复杂度：O(M + N)
整体思路
这段代码旨在解决一个著名的、难度较高的算法问题：寻找两个正序数组的中位数 (Median of Two Sorted Arrays)。中位数是将一个集合划分为两个长度相等的子集，其中一个子集中的所有元素都小于或等于另一个子集中的所有元素。
该算法的核心思想是基于 “划分” (Partitioning)。它试图将两个数组 nums1 和 nums2 分别划分为左、右两部分，使得：
- “左半部分”所有元素的个数总和等于“右半部分”所有元素的个数总和（或多一个）。
- “左半部分”中的最大元素小于或等于“右半部分”中的最小元素。
一旦找到这样完美的划分，中位数就可以直接从划分边界的四个元素（左半部分的最大值们和右半部分最小值们）中得出。
然而，此代码的实现方式存在一个重大的效率问题。虽然它正确地构思了划分的思想，但它没有使用二分查找来寻找这个完美的划分点，而是采用了线性扫描。
具体逻辑步骤如下：
-
预处理：
- 首先，代码确保
nums1是两个数组中较短的那个。这是一个针对二分查找的优化，但在此线性扫描实现中影响不大。 - 然后，它创建了两个新的、更大的数组
a和b，并在它们的头尾分别添加了Integer.MIN_VALUE和Integer.MAX_VALUE作为 哨兵（Sentinels）。这样做的目的是为了在处理划分边界时，无需编写繁琐的if语句来检查是否越界。例如，如果划分点i在a的最左边，那么其左侧最大值就是MIN_VALUE。
- 首先，代码确保
-
线性扫描寻找划分：
- 算法初始化了两个划分索引
i和j。i是在a中的划分位置，j是在b中的划分位置。它们的关系被j = (m + n + 1) / 2 - i隐式定义，以确保左右两半部分的总元素个数平衡。 - 代码从
i=0开始，进入一个while(true)循环。 - 在循环的每一步，它检查当前的划分
(i, j)是否是完美的。完美的条件是a[i] <= b[j+1]并且b[j] <= a[i+1]（代码中写作a[i+1] > b[j]）。 - 如果条件不满足，它并不像二分查找那样跳跃式地调整
i，而是简单地执行i++和j--，即将划分点向右线性移动一位，然后再次检查。
- 算法初始化了两个划分索引
-
计算中位数：
- 一旦
while循环找到了满足条件的划分，就说明找到了正确的位置。 - 此时，整个“左半部分”的最大值是
max(a[i], b[j])。 - 整个“右半部分”的最小值是
min(a[i+1], b[j+1])。 - 如果总元素个数
m+n是奇数，中位数就是左半部分的最大值。 - 如果总元素个数是偶数，中位数就是（左半部分最大值 + 右半部分最小值）/ 2。
- 一旦
总结：这是一个逻辑上部分正确但实现效率低下的解法。它正确地识别了中位数的划分条件，但用了 O(N) 的线性扫描去寻找划分点，而非 O(log N) 的二分查找。
完整代码
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 确保 nums1 是较短的数组，这是一个针对二分查找的优化，但在此处作用不大if (nums1.length > nums2.length) {int[] tmp = nums1;nums1 = nums2;nums2 = tmp;}int m = nums1.length;int n = nums2.length;// 创建新的、带哨兵的数组 a 和 b，以简化边界条件的处理int[] a = new int[m + 2];int[] b = new int[n + 2];// 数组头部填充最小值作为哨兵a[0] = b[0] = Integer.MIN_VALUE;// 数组尾部填充最大值作为哨兵a[m + 1] = b[n + 1] = Integer.MAX_VALUE;// 将原始数组数据复制到新数组的中间部分System.arraycopy(nums1, 0, a, 1, m);System.arraycopy(nums2, 0, b, 1, n);// 初始化划分点 i 和 j。i 从 0 开始，j 根据总长度计算得出int i = 0;int j = (m + n + 1) / 2; // j 是根据 i=0 计算出的初始值// 【效率瓶颈】使用无限循环进行线性扫描，而不是二分查找while (true) {// 检查当前划分是否满足中位数条件：// a[i] 是 nums1 左半部分的最大值// b[j] 是 nums2 左半部分的最大值// a[i+1] 是 nums1 右半部分的最小值// b[j+1] 是 nums2 右半部分的最小值// 条件：左半部分最大值 <= 右半部分最小值if (a[i] <= b[j + 1] && a[i + 1] > b[j]) { // 等价于 b[j] < a[i+1]// 找到了正确的划分int max1 = Math.max(a[i], b[j]); // 整个左半部分的最大值int min2 = Math.min(a[i + 1], b[j + 1]); // 整个右半部分的最小值// 根据总长度的奇偶性计算中位数if ((m + n) % 2 > 0) { // 总长度为奇数return max1;} else { // 总长度为偶数return (max1 + min2) / 2.0;}}// 如果当前划分不满足条件，则线性地移动划分点// 将 nums1 的划分点向右移动一位，nums2 的划分点相应地向左移动一位i++;j--;}}
}
时空复杂度
时间复杂度：O(M + N)
- 数组复制：
System.arraycopy操作需要复制m和n个元素，这部分的时间复杂度是 O(M + N)。 - 主循环：
while (true)循环的本质是一个线性扫描。- 循环变量
i从0开始，每次递增1，直到找到满足条件的划分。在最坏的情况下，i可能需要遍历整个nums1的长度，即M次。 - 因此，循环部分的时间复杂度是 O(M)。
综合分析：
算法的总时间复杂度由数组复制和线性扫描组成：O(M + N) + O(M)。由于 M <= N，所以总的时间复杂度为 O(M + N)。这远劣于此问题的标准最优解法 O(log(min(M, N)))。
空间复杂度：O(M + N)
- 主要存储开销：算法创建了两个新的整型数组
a和b。 - 空间大小：
a的长度是m + 2。b的长度是n + 2。
- 综合分析：
- 算法所需的额外空间由这两个新数组决定。总的额外空间是
(m+2) + (n+2)，即 O(M + N)。 - 这同样是次优的，因为最优解法可以做到 O(1) 的额外空间复杂度。
- 算法所需的额外空间由这两个新数组决定。总的额外空间是
参考灵神