[LeetCode] 88. Merge Sorted Array - 문제풀이

Description

정렬된 두개의 배열을 합쳐서 하나의 정렬된 배열을 만드는 문제입니다.

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

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.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Solution 1. Two Pointers

public void merge(int[] nums1, int m, int[] nums2, int n) {

    int len = nums1.length;
    int idx1 = m-1; // nums1 last value index
    int idx2 = n-1; // nums2 last value index
    for (int i = len-1; i >= 0 && idx1 >=0 && idx2 >=0; i--) { // nums1 끝에서부터 채워넣음
        if(nums1[idx1] >= nums2[idx2]){
            nums1[i] = nums1[idx1--];
        }else{
            nums1[i] = nums2[idx2--];
        }
    }

    while(idx2 >= 0){ // 배열2가 남으면 배열1에 순차적으로 채워줌
        nums1[idx2] = nums2[idx2--];
    }
}

두개의 포인터를 이용하여 한쪽 배열의 요소를 다 비울때 까지 nums1 num2 의 마지막 값 부터 역순으로 스캔하며 큰 수를 0이 채워져있는 nums1의 마지막 부터 채워줍니다. 두번째 배열을 의 요소를 모두 머지했다면(idx2 = -1) 그대로 반환 하면 되고 두번째 요소에 머지할 값이 남았다면 이미 정렬된 상태기 때문에 nums1 요소에 시작부터 그대로 채워넣어주면 됩니다.

• 시간 복잡도 : O(M+N)
• 공간 복잡도 : O(1)

Reference

Merge Sorted Array - LeetCode