LeetCode: 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?

 

 

오늘도 역시 문제를 풀어보았다. 

 

오늘 푼 문제는 merge sort array라는 문제로 merge sort를 알면 쉽게 풀 수 있는 문제이다.

 

처음에 num1, num2가 이미 정렬된 줄 모르고 처음부터 정렬을 시키려고 해서 시간초과가 났다. 

 

이 문제는 O(M+N)안에 풀어야 정답으로 인정이 된다.

 

전체 구간을 정렬시키면 O((M+N)log(M+N))이 되므로 시간초과가 나는 것이다!

 

역시 이 문제도 nums1에 연결된 주소로 답을 인지하는 것 같다. 

 

따로 할당받은 주소로 num1의 pointer를 변경시키면 정답으로 인정이 안된다.

 

왜냐 처음에 연결되어 있는 주소로 정답을 체크하기 때문

 

따라서 in place하게 계산을 해야 한다.

 

이때 list가 이미 정렬되어 있기 때문에, 재귀적인 방법을 사용할 필요없이 바로 merge sort를 시행하면 된다. 

 

하지만 별도의 list로 받는 것이 아닌 nums1에 받아서 출력하는 것이다. 

 

m 은 0을 제외한 list의 길이 n은 num2의 길이이다. 

 

nums1은 m+n의 길이를 가지고 있기 때문에 num1의 마지막 부터 정렬을 시작하면 모든 수 비교가 가능하다.

 

왜냐 0은 n만큼 있기 때문에 포인터를 두 개 사용하여 둘 중 큰 값을 nums1의 오른쪽 끝에 위치시키고 포인터를 감소시키는 행위를 반복하더라도 결국 nums1의 값이 삭제되지는 않기 때문이다. 

 

수도코드는 다음과 같다. 

 

l, r = m, n

p  = m + n -1 (nums1의 마지막 index)

 

while l, r이 모두 0보다 크거나 같을 때까지

       if nums1[l] > nums2[r]:

              nums1[p] = nums1[l]

               l -= 1

               p -= 1 # 두 포인터 모두 사용했기 때문에 1씩 감소

else:
                nums1[p] = nums2[r]
                r -= 1
                p -= 1
남은 list들을 num1에 삽입한 값보다 작은 값이기 때문에 전부 순서대로 넣으면 된다.(이미 정렬된 list)
        while l >= 0:
            nums1[p] = nums1[l]
            l -= 1
            p -= 1
        while r >= 0:
            nums1[p] = nums2[r]
            r -= 1
            p -= 1

        return nums1

 

---

 

구현 코드

 

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        l, r = m-1, n-1
        p = m + n -1
        
        while l >=0 and r >= 0:
            if nums1[l] > nums2[r]:
                nums1[p] = nums1[l]
                l -= 1
                p -= 1
            else:
                nums1[p] = nums2[r]
                r -= 1
                p -= 1

        while l >= 0:
            nums1[p] = nums1[l]
            l -= 1
            p -= 1
        while r >= 0:
            nums1[p] = nums2[r]
            r -= 1
            p -= 1

        return nums1