寻找两个正序数组的中位数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

本人提交代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 合并完的新数组最后一个元素
        int newEnd = m + n - 1;
        int end = m - 1;
        int tail = n - 1;
        while( tail >= 0 )
        {
            // 移动把旧元素拷贝到新数组如果这个比num2中的数都大
            while( end >= 0 && nums2[tail] < nums1[end] )
            {
                nums1[newEnd--] = nums1[end--];
            }
            
            // 找到了插入位置，直接把num2中的最后的那个数字放到新数组
            if ( newEnd >= 0 )
                nums1[newEnd--] = nums2[tail];

            // Next one，开始合并前一个数字
            tail--;
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size() + nums2.size();
        int size1 = nums1.size();
        for ( int i = 0; i < nums2.size(); i++ )
            nums1.push_back( 0 );

        merge( nums1, size1, nums2, nums2.size() );

        int mid = totalLength / 2;
        
        return (totalLength % 2 == 0) ? (nums1[mid] + nums1[mid-1]) * 0.5f : nums1[mid];
    }
};

本文由 BeijingJW 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jun 2, 2023 at 05:22 pm