寻找两个正序数组的中位数：五种实现方案详解

3.算法设计与实现

3.1 二分查找分割法（标准解法）

核心思想：

在两个有序数组中寻找一个分割点，使得左边所有元素都小于等于右边所有元素，并且左边元素个数等于总长度的一半（或一半加一）。

算法思路：

1. 确保 nums1 是较短的数组，如果不是则交换
2. 设总长度 total = m + n，计算中位数位置 leftCount = (total + 1) / 2
3. 在 nums1 中使用二分查找，寻找分割点 i，使得 nums1[0..i-1] 和 nums2[0..j-1] 组成左半部分，其中 j = leftCount - i
4. 需要满足的条件：
   • nums1[i-1] <= nums2[j]（左边最大值小于等于右边最小值）
   • nums2[j-1] <= nums1[i]（同理）
5. 当条件满足时，根据总长度的奇偶性计算中位数：
   • 奇数：max(nums1[i-1], nums2[j-1])
   • 偶数：(max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums2[j])) / 2.0

Java 代码实现：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保 nums1 是较短的数组，这样可以减少二分查找的范围
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        int leftCount = (total + 1) / 2; // 左半部分应有的元素个数
        
        // 在 nums1 的 [0, m] 范围内进行二分查找
        int left = 0, right = m;
        while (left <= right) {
            // i 表示 nums1 中分到左半部分的元素个数
            int i = left + (right - left) / 2;
            // j 表示 nums2 中分到左半部分的元素个数
            int j = leftCount - i;
            
            // nums1 左半部分的最大值，如果 i=0 则为负无穷
            int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            // nums1 右半部分的最小值，如果 i=m 则为正无穷
            int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
            // nums2 左半部分的最大值，如果 j=0 则为负无穷
            int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            // nums2 右半部分的最小值，如果 j=n 则为正无穷
            int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];
            
            // 检查分割是否有效
            if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
                // 找到正确的分割
                if (total % 2 == 1) {
                    // 总长度为奇数，中位数为左半部分的最大值
                    return Math.max(nums1LeftMax, nums2LeftMax);
                } else {
                    // 总长度为偶数，中位数为左半部分最大值和右半部分最小值的平均值
                    int leftMax = Math.max(nums1LeftMax, nums2LeftMax);
                    int rightMin = Math.min(nums1RightMin, nums2RightMin);
                    return (leftMax + rightMin) / 2.0;
                }
            } else if (nums1LeftMax > nums2RightMin) {
                // nums1 的左半部分太大，需要减少 i
                right = i - 1;
            } else {
                // nums1 的左半部分太小，需要增加 i
                left = i + 1;
            }
        }
        // 理论上不会执行到这里
        return 0.0;
    }
}

性能分析：

• 时间复杂度：O(log(min(m, n)))，因为我们在较短的数组上进行二分查找
• 空间复杂度：O(1)，只使用了常数个变量
• 优点：效率高，满足 O(log(m+n)) 的要求，是标准解法
• 缺点：边界条件处理复杂，需要仔细理解

3.2 寻找第 k 小元素（递归二分）

核心思想：

将问题转化为寻找两个有序数组中的第 k 小元素，使用递归方法每次排除掉 k/2 个元素。

算法思路：

1. 定义函数 findKth(nums1, start1, end1, nums2, start2, end2, k)，用于在两个数组的指定范围内寻找第 k 小的元素
2. 如果某个数组的起始位置超过结束位置，则第 k 小元素就在另一个数组中
3. 如果 k==1，返回两个数组起始位置的最小值
4. 否则，分别取两个数组中第 k/2 个元素（如果数组长度不足 k/2，则取最后一个元素）：
   • 如果 nums1[mid1] <= nums2[mid2]，说明 nums1 的前 len1 个元素都不可能是第 k 小的元素，排除它们
   • 否则，排除 nums2 的前 len2 个元素
5. 递归调用，k 减去排除的元素个数

Java 代码实现：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        if (total % 2 == 1) {
            // 奇数长度，返回第 (total+1)/2 小的元素
            return findKth(nums1, 0, m - 1, nums2, 0, n - 1, (total + 1) / 2);
        } else {
            // 偶数长度，返回第 total/2 和 total/2+1 小的元素的平均值
            double left = findKth(nums1, 0, m - 1, nums2, 0, n - 1, total / 2);
            double right = findKth(nums1, 0, m - 1, nums2, 0, n - 1, total / 2 + 1);
            return (left + right) / 2.0;
        }
    }
    
    // 在 nums1[start1..end1] 和 nums2[start2..end2] 中寻找第 k 小的元素
    private double findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        // 计算两个数组当前的长度
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        
        // 确保 nums1 是较短的数组，简化处理
        if (len1 > len2) {
            return findKth(nums2, start2, end2, nums1, start1, end1, k);
        }
        
        // 如果 nums1 为空，则第 k 小元素在 nums2 中
        if (len1 == 0) {
            return nums2[start2 + k - 1];
        }
        
        // 如果 k==1，返回两个数组第一个元素中的较小值
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        
        // 计算两个数组中需要比较的位置
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;
        
        // 递归排除元素
        if (nums1[i] <= nums2[j]) {
            // 排除 nums1 的前 i-start1+1 个元素
            return findKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        } else {
            // 排除 nums2 的前 j-start2+1 个元素
            return findKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
    }
}

性能分析：

• 时间复杂度：O(log(m+n))，每次递归排除 k/2 个元素
• 空间复杂度：O(log(m+n))，递归调用栈深度
• 优点：思路直观，容易理解递归过程
• 缺点：递归调用有栈溢出风险，但本题数据规模下安全

3.3 合并数组（不满足要求，但作为对比）

核心思想：

合并两个有序数组，然后直接找到中位数。虽然简单，但时间复杂度为 O(m+n)，不满足题目要求。

算法思路：

1. 创建一个新的数组，大小为 m+n
2. 使用双指针法合并两个有序数组
3. 根据合并后数组的长度计算中位数

Java 代码实现：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;
        
        // 合并两个有序数组
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        
        // 复制剩余元素
        while (i < m) {
            merged[k++] = nums1[i++];
        }
        while (j < n) {
            merged[k++] = nums2[j++];
        }
        
        // 计算中位数
        int total = m + n;
        if (total % 2 == 1) {
            return merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
}

性能分析：

• 时间复杂度：O(m+n)，需要遍历两个数组的所有元素
• 空间复杂度：O(m+n)，需要额外的合并数组
• 优点：代码简单，易于实现
• 缺点：不满足 O(log(m+n)) 的时间复杂度要求

3.4 改进的二分查找（迭代版本）

核心思想：

将解法二的递归版本改为迭代版本，避免递归调用栈的开销。

算法思路：

1. 使用循环代替递归，不断排除元素直到找到第 k 小元素
2. 每次比较两个数组中第 k/2 个元素，排除较小的那一部分
3. 更新 k 值和数组的起始位置

Java 代码实现：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        if (total % 2 == 1) {
            return findKthIterative(nums1, nums2, (total + 1) / 2);
        } else {
            double left = findKthIterative(nums1, nums2, total / 2);
            double right = findKthIterative(nums1, nums2, total / 2 + 1);
            return (left + right) / 2.0;
        }
    }
    
    private double findKthIterative(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int index1 = 0, index2 = 0;
        while (true) {
            // 边界情况处理
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // 计算需要比较的位置
            int newIndex1 = Math.min(index1 + k / 2, m) - 1;
            int newIndex2 = Math.min(index2 + k / 2, n) - 1;
            
            if (nums1[newIndex1] <= nums2[newIndex2]) {
                // 排除 nums1 的一部分元素
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                // 排除 nums2 的一部分元素
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

性能分析：

• 时间复杂度：O(log(m+n))，每次循环排除 k/2 个元素
• 空间复杂度：O(1)，只使用常数个变量
• 优点：避免递归开销，效率更高
• 缺点：循环逻辑相对复杂

3.5 基于中位数性质的解法

核心思想：

利用中位数的性质，分别找到两个数组的中位数，通过比较它们来缩小搜索范围。

算法思路：

1. 分别找到两个数组的中位数：median1 和 median2
2. 如果 median1 == median2，那么这个值就是中位数
3. 如果 median1 < median2，说明中位数在 nums1 的右半部分和 nums2 的左半部分
4. 如果 median1 > median2，说明中位数在 nums1 的左半部分和 nums2 的右半部分
5. 递归或迭代缩小搜索范围

Java 代码实现：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 确保 nums1 是较短的数组
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0, right = m;
        int halfLen = (m + n + 1) / 2;
        while (left <= right) {
            int i = (left + right) / 2;
            int j = halfLen - i;
            if (i < right && nums2[j - 1] > nums1[i]) {
                // i 太小，需要增大
                left = i + 1;
            } else if (i > left && nums1[i - 1] > nums2[j]) {
                // i 太大，需要减小
                right = i - 1;
            } else {
                // i 合适，计算中位数
                int maxLeft;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }
                int minRight;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i], nums2[j]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}

性能分析：

• 时间复杂度：O(log(min(m, n)))
• 空间复杂度：O(1)
• 优点：基于中位数性质，直观易懂
• 缺点：实现相对复杂

4.性能对比

4.1 复杂度对比表

4.2 实际性能测试

测试环境：JDK 17，数组长度 m=500, n=500，随机生成有序数据，运行 10000 次取平均值

4.3 各场景适用性分析

1. 面试场景：推荐二分查找分割法，展示对问题的深刻理解
2. 竞赛场景：推荐迭代寻找第 k 小，避免递归开销，效率高
3. 生产环境：推荐二分查找分割法，经过充分测试，可靠性高
4. 练习场景：推荐递归寻找第 k 小，易于理解算法思想
5. 小规模数据：合并数组方法简单直接，易于实现和维护

5.扩展与变体

5.1 寻找两个有序数组中的第 k 小元素

题目描述：给定两个有序数组，找到它们中第 k 小的元素。

Java 代码实现：

class Solution {
    public int findKthSortedArrays(int[] nums1, int[] nums2, int k) {
        return findKthIterative(nums1, nums2, k);
    }
    
    private int findKthIterative(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int index1 = 0, index2 = 0;
        while (true) {
            // 边界情况处理
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // 计算需要比较的位置
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, m) - 1;
            int newIndex2 = Math.min(index2 + half, n) - 1;
            
            if (nums1[newIndex1] <= nums2[newIndex2]) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

5.2 寻找多个有序数组的中位数

题目描述：给定 k 个有序数组，找到它们的中位数。

Java 代码实现：

import java.util.PriorityQueue;

class Solution {
    // 使用最小堆合并 k 个有序数组，然后找到中位数
    public double findMedianSortedArrays(int[][] arrays) {
        // 计算总长度
        int total = 0;
        for (int[] arr : arrays) {
            total += arr.length;
        }
        
        // 使用最小堆合并数组
        PriorityQueue<Element> pq = new PriorityQueue<>((a, b) -> a.value - b.value);
        
        // 初始化堆，将每个数组的第一个元素加入
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                pq.offer(new Element(arrays[i][0], i, 0));
            }
        }
        
        // 合并数组
        int[] merged = new int[total];
        int index = 0;
        while (!pq.isEmpty()) {
            Element current = pq.poll();
            merged[index++] = current.value;
            
            // 如果当前数组还有下一个元素，将其加入堆中
            if (current.col + 1 < arrays[current.row].length) {
                pq.offer(new Element(arrays[current.row][current.col + 1], current.row, current.col + 1));
            }
        }
        
        // 计算中位数
        if (total % 2 == 1) {
            return merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
    
    class Element {
        int value;
        int row;
        int col;
        
        Element(int value, int row, int col) {
            this.value = value;
            this.row = row;
            this.col = col;
        }
    }
}

5.3 在两个有序数组中寻找第 k 小的元素对和

题目描述：给定两个有序数组，从每个数组中各取一个数，形成元素对。找到第 k 小的元素对和。

Java 代码实现：

class Solution {
    public int kthSmallestPairSum(int[] nums1, int[] nums2, int k) {
        // 先对数组排序（如果未排序）
        // 使用最小堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] + a[1]) - (b[0] + b[1]));
        
        // 初始化堆，将每个 nums1 元素与 nums2 的第一个元素配对
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            pq.offer(new int[]{nums1[i], nums2[0], 0});
        }
        
        // 弹出 k-1 个最小对
        for (int i = 0; i < k - 1; i++) {
            int[] current = pq.poll();
            int nums1Val = current[0];
            int nums2Val = current[1];
            int nums2Index = current[2];
            
            // 如果当前对中 nums2 的元素不是最后一个，将下一个对加入堆中
            if (nums2Index + 1 < nums2.length) {
                pq.offer(new int[]{nums1Val, nums2[nums2Index + 1], nums2Index + 1});
            }
        }
        
        // 第 k 小的对
        int[] result = pq.peek();
        return result[0] + result[1];
    }
}

5.4 在两个有序数组中找到最接近目标值的和

题目描述：给定两个有序数组和一个目标值，从每个数组中各取一个数，使它们的和最接近目标值。

Java 代码实现：

class Solution {
    public int[] closestPair(int[] nums1, int[] nums2, int target) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[]{-1, -1};
        }
        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = n - 1;
        int minDiff = Integer.MAX_VALUE;
        int[] result = new int[2];
        
        while (left < m && right >= 0) {
            int sum = nums1[left] + nums2[right];
            int diff = Math.abs(sum - target);
            if (diff < minDiff) {
                minDiff = diff;
                result[0] = nums1[left];
                result[1] = nums2[right];
            }
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                // 找到完全相等的和
                break;
            }
        }
        return result;
    }
}

6.总结

6.1 核心思想总结

1. 问题转化：寻找中位数可以转化为寻找第 k 小元素的问题
2. 二分查找：利用数组的有序性，通过二分查找每次排除一半的元素
3. 分割点概念：在两个数组中寻找合适的分割点，使得左边所有元素小于等于右边所有元素
4. 边界处理：需要仔细处理数组为空、分割点在边界等特殊情况
5. 奇偶统一：通过寻找第 k 和 k+1 小元素，统一处理奇数和偶数情况

6.2 实际应用场景

1. 数据库优化：在多个有序索引中快速查找中位数或分位数
2. 数据分析：在多个有序数据流中实时计算中位数
3. 系统监控：在多指标监控系统中计算性能指标的中位数
4. 机器学习：在特征工程中处理多个有序特征的中位数
5. 统计计算：在大规模数据集中快速计算统计量

6.3 面试建议

1. 掌握核心解法：二分查找分割法是必须掌握的
2. 理解原理：能够解释为什么比较分割点可以找到中位数
3. 处理边界：注意处理数组为空、分割点在边界的情况
4. 复杂度分析：能够清晰分析时间复杂度和空间复杂度
5. 手写代码：能够手写二分查找分割法的代码

6.4 常见面试问题 Q&A

Q1：为什么时间复杂度是 O(log(min(m, n)))？
A1：因为我们在较短的数组上进行二分查找，每次将搜索范围减半，所以时间复杂度是对数级别的。

Q2：如何处理数组为空的情况？
A2：如果其中一个数组为空，那么中位数就在另一个数组中，直接根据长度奇偶性计算即可。

Q3：为什么比较 nums1[i-1] 和 nums2[j]，以及 nums2[j-1] 和 nums1[i]？
A3：这是为了确保分割点正确：左边所有元素都小于等于右边所有元素。如果 nums1[i-1] > nums2[j]，说明左边有元素太大，需要减少 i；如果 nums2[j-1] > nums1[i]，说明左边有元素太大，需要增加 i。

Q4：这个算法能否扩展到多个有序数组？
A4：可以，但复杂度会更高。可以使用堆来合并多个数组，或者使用二分查找在多个数组中寻找第 k 小元素，但实现会更复杂。

Q5：如果数组中有重复元素，这个算法还能用吗？
A5：可以。算法不依赖于元素是否重复，只要数组是有序的就可以使用。