[LeetCode] 88. Merge Sorted Array - Java

 

Merge Sorted Array - LeetCode

 

문제

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of 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.

 

Constraints:

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

 

정렬된 두개의 배열 nums1과 nums2를 nums1에 정렬된 상태로 병합하는 문제이다.

각 배열의 원소의 개수는 m과 n으로 주어진다.

 

---

 

내 풀이

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        for(int i=0; i<n; i++){
            nums1[m+i] = nums2[i];
        }

        for(int i=1; i<nums1.length; i++){
            int num = nums1[i];
            int prev = i-1;
            while((prev>=0) && (nums1[prev]>num)){
                nums1[prev+1] = nums1[prev];
                prev--;
            }
            nums1[prev+1] = num;
        }
    }
}

삽입 정렬을 사용해서 풀었다.

nums1에 nums2의 값을 일단 넣어주고, nums1에 대해 삽입 정렬을 실행했다.

삽입정렬은 2번째 원소부터 시작하여 앞의 원소들과 비교하여 삽입할 위치를 정한 후, 원소들을 뒤로 옮기고 정해진 위치에 해당원소를 삽입하는 정렬이다.

1. 반복문을 돌며 각 위치의 값을 temp 에 저장한다.
2. 해당 위치 이전에 있는 원소들과 비교하여 temp보다 값이 크다면 자리를 바꾸며 삽입한다.

• 시간복잡도
  • 최악의 경우 : O(n^2) - 역으로 정렬되어 있을 경우
  • 최선의 경우 : 각 단계에서 한번씩만 비교를 하므로 O(n)
• 공간복잡도 : O(1) - 주어진 배열에서 자리를 교환하므로 제자리정렬

 

---

 

다른 풀이

투 포인터 사용

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--];
            }
        }
    }
}

각각 m-1 과 n-1 로 초기화된 포인터 i와 j를 사용하여 풀이가 가능하다.

nums1과 nums2의 뒤에서부터 포인터를 사용하여 원소를 비교하여 nums2의 모든 원소를 nums1의 적절한 자리에 삽입할 수 있다.

• 시간복잡도 : O(n)
• 공간복잡도 : O(1)