力扣第44题：寻找两个正序数组的中位数 - 合并排序解法详解

内容简介

本文详细解析了力扣第44题"寻找两个正序数组的中位数"的合并排序解法。通过双指针技术合并两个有序数组，然后直接计算合并后数组的中位数。虽然时间复杂度为O(m+n)，但这种方法思路清晰，代码简洁，是理解该问题的基础解法。文章包含完整注释代码、算法思路讲解和复杂度分析。

算法思路

‌1.合并两个有序数组‌：使用双指针(min1和min2)分别遍历nums1和nums2

2‌.比较元素大小‌：每次取两个指针所指元素的较小值放入合并数组

‌3.处理剩余元素‌：当某个数组遍历完后，直接将另一个数组剩余元素加入

‌4.计算中位数‌：根据合并后数组长度的奇偶性返回相应中位数值

完整代码（带注释）

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums;  // 存储合并后的有序数组
        int min1 = 0;      // nums1的遍历指针
        int min2 = 0;      // nums2的遍历指针
        
        // 合并两个有序数组
        while(min1 != nums1.size() || min2 != nums2.size()) {
            // 处理nums2已遍历完的情况
            if(min2 == nums2.size()) {
                nums.push_back(nums1[min1]);
                min1++;
            }
            // 处理nums1已遍历完的情况
            else if(min1 == nums1.size()) {
                nums.push_back(nums2[min2]);
                min2++;
            }
            // 两个数组都还有元素时比较大小
            else {
                // 取当前两个指针位置的较小值
                int n = nums1[min1] < nums2[min2] ? nums1[min1] : nums2[min2];
                nums.push_back(n);
                // 移动较小值所在数组的指针
                n == nums1[min1] ? min1++ : min2++;
            }
        }

        // 计算合并后数组的中位数
        if(nums.size() % 2) {  // 数组长度为奇数
            return nums[nums.size()/2];
        }
        else {  // 数组长度为偶数
            int tmp1 = nums[nums.size()/2];      // 中间右侧元素
            int tmp2 = nums[nums.size()/2-1];    // 中间左侧元素
            return (tmp1 + tmp2) / 2.0;          // 返回平均值
        }
    }
};

复杂度分析

‌时间复杂度‌：O(m+n)，需要完整遍历两个输入数组的所有元素

‌空间复杂度‌：O(m+n)，需要额外空间存储合并后的数组

优化方向

虽然这种解法易于理解，但可以通过以下方法进一步优化：

‌二分查找法‌：将时间复杂度优化到O(log(min(m,n)))

‌不实际合并数组‌：通过虚拟索引直接找到中位数位置，节省空间

总结

本文提供的合并排序解法是解决两个有序数组中位数问题的基础方法，代码简洁明了，适合作为学习该问题的入门方案。理解这种解法后，可以进一步探索更高效的二分查找解法。