for Robot Artificial Inteligence

32. Merge Sorted Array

06 Jul 2020 | Daily Algorithms

My Solution

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        unordered_map<int,int> mp;
        vector<int> result;
        if(nums1.size()<1 || nums2.size()<1)
        {
            return;
        }
        int max =0;
        if(nums1[0]<0 || nums2[0]<0)
        {
            for(int i =0; i<m;i++)
            {
                mp[nums1[i]+1]+=1;
                if(nums1[i]>max)
                    max = nums1[i];
            }            
            for(int i=0; i<n;i++)
            {
                mp[nums2[i]+1]+=1;
                if(nums2[i]>max)
                    max = nums2[i];
            }
            int i =0;
            int size_ = m+n;
            int iter = (max>size_)?max:size_;
            cout<<iter;
            while(i<=iter+1)
            {
                if(mp[i]>=1)
                {
                    result.push_back(i-1);
                    mp[i]--;
                }
                else
                {
                    i++;
                }
            }
        }
        else
        {
            for(int i =0; i<m;i++)
            {
                mp[nums1[i]]+=1;
                if(nums1[i]>max)
                    max = nums1[i];
            }
            for(int i=0; i<n;i++)
            {
                mp[nums2[i]]+=1;
                if(nums2[i]>max)
                    max = nums2[i];
            }
            int i =0;
            int size_ = m+n;
            int iter = (max>size_)?max:size_;
            while(i<=iter+1)
            {
                if(mp[i]>=1)
                {
                    result.push_back(i);
                    mp[i]--;
                }
                else
                {
                    i++;
                }
            }
        }

        nums1=result;


    }
};

other

  • This code relies on the simple observation that once all of the numbers from nums2 have been merged into nums1, the rest of the numbers in nums1 that were not moved are already in the correct place
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m-1;
        int j = n-1;
        int tar =m+n-1; // calculate the index of the last element of the merged array

        // go from the back by A and B and compare and put to the A element which is larger
        // 뒤에서부터 채운다
        while(j>=0)
        {
            nums1[tar--] = (i>=0 && nums1[i]>nums2[j])?nums1[i--]:nums2[j--];
        }


    }
};

Comments