[리트코드] 88. Merge Sorted Array

문제

https://leetcode.com/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

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.

---

✔ 문제접근 #1 투포인터[통과] ⭕

Intuition
두개의 배열은 모두 오름차순으로 정렬 되어 있다.

두개의 배열의 시작점을 포인터로 하여 앞에서부터 포인터 위치의 값을 비교하여 작은 숫자를 nums1배열에 앞부분 부터 채워준다.

Algorithm
두개의 배열의 시작점에 각각 p1, p2의 포인터를 갖는다. 그리고 nums1의 삽입할 위치 idx를 갖는다.

p1, p2를 비교하여 더 작은 숫자를 nums1 배열의 idx위치에 넣는다. 그리고 더 작은 숫자가 있었던 쪽읜 포인터 p1을 +1 증가시키고, idx 도 +1 증가 시킨다.

이렇게 병합정렬에서 사용하는 merge알고리즘을 사용하여 오름차순으로 배열을 만들 수 있다.

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:

        # 병합정렬 -> nums1에 넣어주기
        # [1, 2, 3, 0, 0, 0] [2, 5, 6]

        p1, p2, idx = m - 1, n - 1, m + n - 1
        
        while p1 >= 0  and p2 >= 0:
            if nums1[p1] >= nums2[p2]:
                nums1[idx] = nums1[p1]
                idx -= 1
                p1 -= 1
            elif nums1[p1] < nums2[p2]:
                nums1[idx] = nums2[p2]
                idx -= 1
                p2 -= 1
        
        # 왼쪽이 남는경우
        if p2 < 0:
            while p1 >= 0:
                nums1[idx] = nums1[p1]
                idx -= 1
                p1 -= 1
        # 오른쪽이 남는경우
        elif p1 < 0:
            while p2 >= 0:
                nums1[idx] = nums2[p2]
                idx -= 1
                p2 -= 1

 

Complexity Analysis

• 시간 복잡도 : O(M + N)
  • num1 배열을 순차탐색 O(M)
  • num2 배열을 순차탐색 O(N)
  • 그러므로 전체시작복잡도 : O(M + N)

• 공간복잡도 : O(1)
  
  • 기존의 num1 배열을 재사용하기 때문에 추가적인 메모리를 사용하지 않는다.

---

기타풀이 및 회고

기존의 병합정렬에서 병합의 경우는 추가적인 배열을 사용하여 데이터를 하나씩 옮기는 방식이었다. 하지만 이번 문제에서는 num1배열을 그대로 사용할 수 있도록 전체 데이터만큼의 크기가 num1의 길이로 주어졌기 때문에 in-place방식으로 해결할 수 있었다.