AC cpp code, time complexity is O(m+n)


  • 0

    The basic thought for this question is compare from rightmost to left, it will not cause data move (insert to left part will cause data index move.)

    class Solution {
    public:
      void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, p = m + n - 1;
    
        while (p >= 0)
        {
          if (i < 0)
          {
            nums1[p] = nums2[j --];
          }
          else if (j < 0)
          {
            nums1[p] = nums1[i --];
          }
          else if (nums1[i] >= nums2[j])
          {
            nums1[p] = nums1[i --];
          }
          else
          {
            nums1[p] = nums2[j --];
          }
          p --;
        }
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.