**Leetcode: Merge Sorted Array (3ms) analysis and solution

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) 

to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

Hide Tags

 Array Two Pointers

Show Similar Problems

Analysis:

1. Understand the problem clear first: merge the nums2 into nums1, which means that it's not a good idea to build the third vector, eg. nums3, to store the new vector. Instead, we need to merge in place.

2. Merge from back to front. This way we avoid the extra element moving operations. Note the condition when i<0;

//////////////////////////////////////////////////
//codes  4ms

class Solution {

public:

       void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

              int index = 0, i = m - 1, j = n - 1;

              //check input

              if (n == 0) return;

              else if (m == 0){ nums1 = nums2; return; }

              while (j>-1){

                     //judge the bigger one

                     if (i<0 || nums2[j] >= nums1[i]){

                           nums1[m + n - 1 - index] = nums2[j];

                           j--;

                     }

                     else {

                           nums1[m + n - 1 - index] = nums1[i];

                           i--;

                     }

                     index++;

              }

       }

};

//////////////////////////////////////////////////////////////////
Revised 3ms
///////////////////////////////////////////////////////////////////

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(j>-1){
            if(i< 0 || nums1[i]<nums2[j]){ //Note: this branch should be put in front
                nums1[k]=nums2[j];
                j--;
                k--;
            }
         
            else{
                nums1[k]=nums1[i];
                i--;
                k--;
            }
         
         
        }
        return;
    }
};