Leetcode skimming 4 Find the median of two positive arrays

Given two sizes, they are m and n Positive order of （ From small to large ） Array nums1 and nums2. Please find and return the values of these two positive ordered arrays Median .

The time complexity of the algorithm should be O(log (m+n)) .

Example 1：

Input ：nums1 = [1,3], nums2 = [2]
Output ：2.00000
explain ： Merge array = [1,2,3] , Median 2

Example 2：

Input ：nums1 = [1,2], nums2 = [3,4]
Output ：2.50000
explain ： Merge array = [1,2,3,4] , Median (2 + 3) / 2 = 2.5

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

In fact, at the beginning, my idea was to combine these two vector Compose one and sort , Then take out the elements of the intermediate index , And return the corresponding median according to the parity bit . But both arrays are ordered , use sort Sort , Quick sort in the face of such a situation , Efficiency is not ideal . therefore , I didn't use this method for efficiency , Instead, we iterate through these two arrays , Increase the counter by one at a time , Until the counter reaches the middle value . This has better spatial complexity

class Solution {
    
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        bool is_odd=(nums1.size()+nums2.size())%2==0?false:true;
        int mid1=0,mid2=0;
        int p=0,q=0;
        int tar=(nums1.size()+nums2.size())/2;
        while(p+q<=tar){
    
            mid1=mid2;
            if(p>=nums1.size()){
    
                mid2=nums2[q];
                q++;
                continue;
            }
             if(q>=nums2.size()){
    
                mid2=nums1[p];
                p++;
                continue;
            }
            if(nums1[p]>nums2[q]){
    
                mid2=nums2[q];
                q++;
            }
            else{
    
                mid2=nums1[p];
                p++;
            }
        }
        if(is_odd){
    return mid2;}
        else{
    return (double)(mid1+mid2)/2;}
    }
};

Later I saw a blog using STL Of marge Sort is to merge and sort two ordered arrays , So we have this method now , It is similar to my initial idea , This method has excellent time complexity

class Solution {
    
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        bool is_odd=(nums1.size()+nums2.size())%2==0?false:true;
        int mid1=0,mid2=0;
        int p=0,q=0;
        vector<int> nums3;
        nums3.resize(nums1.size()+nums2.size());
        merge(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),nums3.begin());
        mid2=nums3[nums3.size()/2];
        if(is_odd){
    return mid2;}
        else{
    
            mid1=nums3[nums3.size()/2-1];
            return (double)(mid1+mid2)/2;
            }
    }
};