[leetcode] 88. Merge Sorted Array

문제 설명

링크
MergeSort

앞에서부터

• 작은 수 부터 넣기
• rotation: [1, 3, 0, 0] -> [0, 0, 1, 3]
• 불필요한 rotation

코드 1

  class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        if n == .zero { return }

        if m > 0 {
            for _ in 0 ... m - 1 {
                nums1.append(nums1.removeFirst())
            }
        } else {
            nums1 = nums2
        }
        var newNums1Index = 0
        var nums1Index = 0
        var nums2Index = 0

        while nums1Index < m && nums2Index < n {
            if nums1[nums1Index + n] < nums2[nums2Index] {
                nums1[newNums1Index] = nums1[nums1Index + n]
                nums1Index += 1
            } else {
                nums1[newNums1Index] = nums2[nums2Index]
                nums2Index += 1
            }
            newNums1Index += 1
        }
        
        while newNums1Index < n + m {
            if nums1Index < m {
                nums1[newNums1Index] = nums1[nums1Index + n]
                nums1Index += 1
            } else if nums2Index < n {
                nums1[newNums1Index] = nums2[nums2Index]
                nums2Index += 1
            }
            newNums1Index += 1
        }
    }
}

뒤에서부터

• 제일 큰 수부터 넣기
• 남은 요소 넣을 필요 없음

코드 2

 class Solution {
     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
         // 뒤에서부터 시작하는 인덱스들
         var i = m - 1      // nums1의 실제 요소 인덱스
         var j = n - 1      // nums2의 인덱스
         var k = m + n - 1  // 결과를 저장할 위치 인덱스
         
         // 두 배열의 요소를 뒤에서부터 비교하여 큰 값을 nums1의 뒤에서부터 채움
         while i >= 0 && j >= 0 {
             if nums1[i] > nums2[j] {
                 nums1[k] = nums1[i]
                 i -= 1
             } else {
                 nums1[k] = nums2[j]
                 j -= 1
             }
             k -= 1
         }
         
         // nums2에 남은 요소가 있다면 복사
         while j >= 0 {
             nums1[k] = nums2[j]
             j -= 1
             k -= 1
         }
         
         // nums1에 남은 요소는 이미 올바른 위치에 있으므로 추가 작업 필요 없음
     }
 }