Merge Sorted Array - LeetCode

Problem

1. input: 정수 배열 nums1, nums2, 두 배열의 원소의 갯수 m, n

2. output: 두 배열을 병합하여 오름차순으로 nums1에 정렬

3. Follow up: Can you come up with an algorithm that runs in O(m + n) time?

   ex)

   

   • nums1.length == m + n
   • nums2.length == n
   • 0 <= m, n <= 200
   • 1 <= m + n <= 200
   • 109 <= nums1[i], nums2[j] <= 109

Idea

단순히 nums1을 복사하고 기존의 nums1를 빈 배열로 생각하여 nums1, nums2의 원소를 앞에서 부터 하나씩 비교하여 삽입하면 O(m+n)에 풀 수 있다 → Sol1

하지만 이 방식은 추가적인 메모리를 필요로 한다. 문제에서 nums1의 원소 뒤에 num2의 크기(n)만큼 0이 삽입된 것을 볼 수 있다. 즉 뒤의 빈공간을 활용하면 된다.

nums1과 nums2의 가장 큰 값부터 작은 값 순으로 비교하여 nums1의 뒷자리에 넣어주면 된다 → Sol2

Solution

1. 추가메모리 사용

   nums1을 복사 → copy

   copy와 nums2의 원소를 앞에서 부터 비교하여 하나씩 nums1에 삽입

   class Solution {
       fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
           val copy = nums1.toList()
           var idx1 = 0
           var idx2 = 0
           while (true) {
               if (idx1 == m) {
                   for (i in idx2 until n) {
                       nums1[idx1 + i] = nums2[i]
                   }
                   break
               }
               if (idx2 == n) {
                   for (i in idx1 until m) {
                       nums1[idx2 + i] = copy[i]
                   }
                   break
               }
               if (copy[idx1]<= nums2[idx2]) {
                   nums1[idx1 + idx2] = copy[idx1++]
               } else {
                   nums1[idx1 + idx2] = nums2[idx2++]
               }
           }
       }
   }
   

   시간 복잡도: copy 순회 + nums2 순회 = n

   

2. 큰값부터 정려

   nums1, nums2의 원소중 큰값부터 nums1의 뒤에 삽입

   class Solution {
       fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
           var i = m - 1
           var j = n - 1
           var k = m + n - 1
   
           while (k >= 0) {
               if (i >= 0 && j >= 0) {
                   if (nums1[i] <= nums2[j]) {
                       nums1[k--] = nums2[j--]
                   } else {
                       nums1[k--] = nums1[i--]
                   }
               } else if (i < 0 && j >= 0) {
                   nums1[k--] = nums2[j--]
               } else {
                   nums1[k--] = nums1[i--]
               }
           }
       }
   }
   

   시간 복잡도: nums1 순회 + nums2 순회 = n

   

Point

1. 주어진 문제의 조건 중, 특이사항에 집중할 것