Skip to main content

Merge Sorted Array

Merge Sorted Array

감소하지 않는 순서로 정렬된 두 개의 정수 배열 nums1 및 nums2와 각각 nums1 및 nums2의 요소 술를 나타내는 두 개의 정수 m 및 n이 제공됩니다. nums1과 nums2를 감소하지 않는 순서로 정렬된 단일 배열로 병합합니다. 최종 정렬된 배열은 함수에 의해 반환되지 않고 대신 배열 nums1 내부에 저장되어야 합니다. 이를 수용하기 위해 nums1의 길이는 m + n입니다. 여기서 첫 번째 m 요소는 병합해야 하는 요소를 나타내고 마지막 n 요소는 0으로 설정되므로 무시해야 합니다. nums2의 길이는 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.

나의 풀이

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
"""
result = nums1[:m] + nums2[:n]
nums1[:m+n] = sorted(result)

nums1 배열과 이 배열의 유효 길이를 나타내는 m, nums2 배열과 이 배열의 유효 길이를 나타내는 n이 인수에 입력되므로 각 배열이 가진 유효 길이만큼 총합한 후에 sorted 함수를 사용하여 오름차순으로 반환된 배열과 동일하게 nums1의 값들을 변경합니다. 즉, 각 배열의 유효한 길이만큼을 잘라서 하나의 배열로 합친 후에 오름차순으로 정렬합니다. 이 코드의 실행 결과 Runtime은 18ms이고 Memory는 13.3MB로 메모리를 다소 소모한 코드입니다.

Runtime이 가장 짧은 코드 (3ms)

class Solution(object):
def merge(self, nums1, m, nums2, n):
# nums의 길이 만큼 반복
for x in range(0, n):
# x에 m의 길이를 더한만큼 i를 초기화하므로
# nums1의 배열에서 m만큼은 그대로 두고 nums2 길이인 n만큼 nums2의 요소를 nums1에 추가
i = x + m
nums1[i] = nums2[x]
# 오름차순 정렬 수행
nums1.sort()
return nums1