Leetcode: Merge Sorted Array, 정렬된 배열 병합하기

문제설명

• 두 정렬된 배열이 주어졌을 때 배열을 병합하라
• 병합된 배열은 오름차순으로 정렬되어야 한다.
• 첫 번째 배열은 두 번째 배열만큼의 크기를 더 갖는다.
• 첫 번째 배열에 병합 결과를 넣는다.

문제풀이

• 가장 쉬운 방법은 첫 번째 배열에 두 번째 배열을 그대로 이어 붙이고 정렬하면 된다. 다만 O(log n)의 시간복잡도를 갖는다.
• 시간 복잡도를 O(N)로 풀려면, 첫번째 배열을 따로 복사하여 두 배열의 항목을 하나씩 비교하여 첫 번째 배열에 넣는다.

func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
    let nums1Copy = Array(nums1)

    var p1 = 0, p2 = 0

    for i in 0..<m+n {
        if p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2]) {
            nums1[i] = nums1Copy[p1]
            p1 += 1
        } else {
            nums1[i] = nums2[p2]
            p2 += 1
        }
    }
}

var nums1: [Int], nums2: [Int]

nums1 = [1,2,3,7,0,0,0]
nums2 = [2,5,6]
merge(&nums1, 4, nums2, 3)
print(nums1) // 1,2,2,3,5,6,7

nums1 = [1]
nums2 = []
merge(&nums1, 1, nums2, 0)
print(nums1) // 1

nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]
merge(&nums1, 3, nums2, 3)
print(nums1) // 1,2,2,3,5,6