[Leet Code풀이] 88. Merge Sorted Array

문제 설명

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

오름차순으로 주어진 두개의 리스트를 오름차순으로 정렬하는 문제이다. 다만 조건이 있는데, nums1 배열에 in-place방식으로 정렬을 해야한다.

풀이

접근 방법

1) 먼저 인풋으로 주어지는 num1의 0,0.. 부분에 nums2의 배열을 복사한다. 2) 복사한 배열을 sort() 함수를 써서 정렬한다.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:] = nums2[:] # [1,2,3,2,5,6],

        nums1.sort() # [1,2,3,2,5,6] #Tim sort O(nlogn)

위 풀이의 시간 복잡도와 공간복잡돈는 아래와 같다.

• 시간 복잡도 : O((m+n)log(m+n)) 파이썬3의 sort()함수는 Tim sort를 사용하며 속도는 O(nlogn) 의 시간 복잡도를 가진다. nums1의 개수 m과 nums2의 개수를 합한 m+n개의 시간 복잡도를 가지게 된다.

• 공간 복잡도 : O(1) 추가적인 공간을 사용하지 않는다.