Day001 - 88. Merge Sorted Array

88. Merge Sorted Array

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
• -109 <= nums1[i], nums2[j] <= 109

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

내 풀이

# 내 풀이
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        for i in range(len(nums1) - m):
            nums1.remove(0)

        nums1.extend(nums2)

        nums1.sort()

간단하게 두 개의 list (nums1과 nums2)를 merge한 후 오름차순 정렬을 해야하는 문제이다.

하지만 특이사항으로 정답을 return하지 말고 nums1 list 자체를 modify하기만 하면 된다.

즉, 주어진 nums1 list 그 자체를 요구사항대로 수정을 하여야 한다는 것.

가장 먼저 떠오르는 방법으로는 nums1과 nums2를 더한 후 sort한 결과를 nums1에 할당하면 된다고 생각해서 제출을 했었는데…

nums1 = sorted(nums1 + nums2)

위와 같은 방법을 사용하면 기존의 nums1이 아닌 새로운 list를 만들어 sorting을 하게 되므로 nums1 list 자체가 바뀌지는 않는다.

따라서 list를 직접 수정하는 방법을 사용하였는데,

1. list.remove()를 이용해 nums1 list 뒷부분의 의미없는 0을 제거한 후
2. list.extend()로 nums1 list 뒤에 nums2 list를 이어붙였고
3. list.sort()를 통해 nums1 list 자체를 sort하였다. (sorted()를 사용하면 nums1의 sorting된 list가 새로 만들어진다.)

• 다른 풀이

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        l, r = 0, 0
        copy1 = deepcopy(nums1)

        for i in range(n+m):
            if r >= n or (l < m and copy1[l] <= nums2[r]):
                nums1[i] = copy1[l]
                l += 1
            else:
                nums1[i] = nums2[r]
                r += 1

다른 방법으로는 left와 right의 pointer를 만들어서 for loop을 순회하며 nums1의 각 요소와 nums2의 요소를 하나씩 대소비교를 하여 nums1의 요소를 nums2의 요소로 직접 바꿔주는 방법이 있다.