LeetCode 88. Merge Sorted Array (Python)

https://leetcode.com/problems/merge-sorted-array/

Merge Sorted Array - LeetCode

Solution 1

• 시간복잡도 : O(NlongN)
• 공간복잡도 : O(N)

아이디어 (정렬)

아주 단순하다. nums1 뒤에 넣고 정렬을 한다. 그리고 일반 할당이 아닌 슬라이스 할당을 하였다.

이렇게 하면 참조(주소)에 의한 호출로 동작하므로 값이 바뀐다.   

 

# 1. 정렬
def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
     for i, v in enumerate(nums2):
        nums1[m+i] = v
     nums1[:] = sorted(nums1)

 

Solution 2 (풀이 가져옴)

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

아이디어 (비교 및 삽입)

이건 생각도 못하고 이해도 어렵다. 

i, j로 비교하고, k로 삽입을 한다. 그리고 j가 아직 남았으면 다시 nums1에 삽입한다...

 

 

# 2. 비교 및 삽입
def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i = m - 1
    j = n - 1
    k = m + n - 1

    while i >= 0 and j >= 0:
        if nums1[i] < nums2[j]:
            nums1[k] = nums2[j]
            j -= 1
        else:
            nums1[k] = nums1[i]
            i -= 1

        k -= 1

    while j >= 0:
        nums1[k] = nums2[j]
        k -= 1
        j -= 1