[LeetCode/Java] 88. Merge Sorted Array

0. 문제

https://leetcode.com/problems/merge-sorted-array/

1. 문제 설명

• 오름차순으로 정렬된 두 정수 배열 nums1, nums2가 주어진다.
• 배열과 함께 nums1 배열의 빈 공간 m과 nums2 배열 원소의 개수 n이 주어진다.
• nums1에 nums2를 병합하는데, 이때 nums1은 오름차순을 유지한다.
• nums1은 m + n개의 길이를 갖는다.

2. 문제 풀이

2.1. 접근법

• nums1 배열의 길이는 m + n이기 때문에 nums2의 모든 배열의 원소가 들어갈 수 있다.
• nums1에 nums2의 모든 원소를 저장한 다음 오름차순 정렬을 하면 된다.

2.2. 의사코드

for (nums1의 빈 공간부터 nums1의 마지막 공간까지)
	nums1의 빈 공간에 nums2의 값 저장

nums1 오름차순 정렬

3. 코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m; i < nums1.length; i++) {
            nums1[i] = nums2[i - m];
        }
        Arrays.sort(nums1);
    }
}

4. 결과

5. 개선점

5.1. 시간 복잡도 개선

• 위 코드의 시간 복잡도를 계산하면 다음과 같다.

  • for() : O(n)
  • sort() : O((m+n) + log(m+n))
  • O(n) + O((m+n) + log(m+n)) ⇒ O((m+n) + log(m+n))

• 시간 복잡도를 개선시키기 위해 투 포인터 알고리즘을 사용할 수 있다. (참고)

• 풀이

  • nums2의 원소 개수만큼 반복
  • nums1의 마지막 원소(a)와 nums2의 마지막 원소(b)를 비교
  • nums1의 빈 공간 마지막 인덱스부터 차례대로 a와 b 중 더 큰 값을 저장
  • 반복문(while)을 한 번 사용하기 때문에 O(n)의 시간 복잡도로 풀이 가능

• 풀이

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

• 결과