[리트코드] 88. Merge Sorted Array - python

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.

두 배열을 합치면서 정렬하기

제한사항

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

풀이

[1,2,3] [2,5,6]

num1에서 m까지 다른 배열과 num2를 비교한다

각각 포인터를 두고 더 작은 것을 결과 배열에 담고 포인터를 옮긴다.

각 포인터가 m,n 보다 작은지 체크하며 옮겨야한다.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        tmp = nums1[:m]
        i, j = 0, 0
        idx = 0
        while i < m and j < n:
            
            if tmp[i] <= nums2[j]:
                nums1[idx] = tmp[i]
                i += 1
            else:
                nums1[idx] = nums2[j]
                j += 1
            idx += 1
        
        while i < m:
            nums1[idx] = tmp[i]
            i += 1
            idx += 1
        
        
        while j < n:
            nums1[idx] = nums2[j]
            j += 1
            idx += 1

굳이 숫자를 분리하지 않고 뒤부터 큰 수끼리 비교해서 넣는 방법이 더 낫다.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        while m > 0 and n > 0:
            if nums1[m-1] >= nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        if n > 0:
            nums1[:n] = nums2[:n]