88. Merge Sorted Array

Source link: https://leetcode.com/problems/merge-sorted-array/

Design

Method I

  1. Initialize pointers i, j for traversing nums1 and nums2, pointer i points to the position m, and pointer j points to the beginning element of nums2.
  2. Replace elements after m in nums1 with values in nums2.
  3. Sort elements inside nums1.

Method II

The idea of this approach is to replace the element inside nums1 with the larger value between nums1 and nums2 from back to front:

  1. Initialize three pointers, one points to the m - 1 position of nums1, another one points to the last element of nums2, and the last one points to the end of nums1.
  2. Traverse from back to front, if the element inside nums1 is larger than nums2, replace the element of position k with nums1’s value, and vice versa.
  3. If there are still elements inside nums2, replace the element of position k with nums2’s value.

Implementation

Method I

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m;
    for (int j = 0; j < n; i++, j++) {
      nums1[i] = nums2[j];
    }
    Arrays.sort(nums1);
  }
}

Method II

class Solution {
  public void merge(int[] nums1, int m, 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 Analysis

Method I

Time: $O(nlogn)$

Space: $O(1)$

Method II

Time: $O(n)$

Space: $O(1)$