[LeetCode] 88 Merge Sorted Array JavaScript

문제 링크

Merge Sorted Array - LeetCode

 

문제 유형

in-place sort

 

문제 풀이

이 문제는 num2 배열을 num1 배열로 합쳐서 비내림차순으로 in-place 정렬한 nums1을 반환해야 한다. 비내림차순(non-decreasing order)란 배열이 내림차순이 아닌 경우를 말한다. 즉, 배열 내에 같은 원소가 있기도 하고 그 원소들이 오름차순으로 정렬되어야 한다.

 

이 문제는 다음과 같은 방법으로 해결할 수 있다.

1. num1과 num2의 정렬되어야 할 가장 끝 원소들을 가리키는 포인터 2개와 num1의 배열 끝 원소를 가리키는 포인터 1개를 설정한다.
2. num1의 정렬되어야 할 원소를 가리키는 포인터가 정렬될 위치를 가리키는 포인터보다 작으면 다음의 과정을 반복한다.
   a) nums1의 원소가 nums2의 원소보다 크면 정렬될 위치에는 nums1의 원소가 들어가고, nums1 포인터를 한칸 앞으로 옮긴다.
   b) nums1의 원소가 nums2의 원소와 같거나 작으면 정렬될 위치에는 nums2의 원소가 들어가고, nums2 포인터를 한칸 앞으로 옮긴다.

 

코드

var merge = function(nums1, m, nums2, n) {
    let idx = nums1.length - 1;
    let m1 = m - 1;
    let n2 = n - 1;
    while (m1 < idx) {
        if (nums1[m1] > nums2[n2]) {
            nums1[idx] = nums1[m1];
            m1--;
        } else {
            nums1[idx] = nums2[n2];
            n2--;
        }
        idx--;
    }
    return nums1;
};

 

참고

https://www.youtube.com/watch?v=V2Pd8DAHXQw