88. Merge Sorted Array

88. Merge Sorted Array

문제

정렬된 두 배열nums1, nums2을 nums1에 병합하는 문제이다. 둘 중 한 배열은 최종적으로 병합될 m + n의 length를 가지고 있고, 나머지는 0으로 채워진다.

테스트 케이스

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

풀이

1. nums1, nums2 배열의 가장 마지막 원소부터 비교한다.
2. 더 큰 원소를 nums1 배열의 끝 k 인덱스에 저장하고, 해당 배열의 인덱스를 하나씩 감소시킨다.
3. 이 과정을 nums1 배열의 인덱스i나 nums2 배열의 인덱스j 중 하나라도 0보다 작아질 때까지 반복한다.
4. nums2 배열의 나머지 원소가 남아있다면, nums1 배열에 저장한다.

시간 복잡도 O(m+n)과 공간 복잡도 O(1)을 가진다.

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */

var merge = function(nums1, m, nums2, n) {
  let 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--]
  }
};