merge sorted array

mail@pastecode.io avatar
unknown
c_cpp
16 days ago
1.2 kB
4
Indexable
Never
complexity time : o(n+m) 
complexity Space : o(1)
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(nums1[i]>nums2[j])
            {
                nums1[k--]=nums1[i--];
            }
            else
            {
                 nums1[k--]=nums2[j--]; 
            }
        }
      while(j>=0)
        {
            nums1[k--] = nums2[j--];
        }
    }
};
_______________________________________________
complexity time o(mLog(m)+nlog(n+m))
complexity space : o(n+m)
using ordered map :
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
     map<int,int> sorted_map;
     for(int i = 0; i < m; i++)
     {
        sorted_map[nums1[i]]++;
     }   
     for(int i =0;i<n;i++)
     {
        sorted_map[nums2[i]]++;
     }
     nums1.clear();
     for(auto itr = sorted_map.begin(); itr != sorted_map.end() ; ++itr)
     {
        while(itr->second--)
        {
            nums1.push_back(itr->first);
        }
     }
    }
};
Leave a Comment