[leetcode] 88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

 

 

---

문제

두 개의 정수 배열 num1 과 num2 가 오름차순으로 정렬되어 주어지고 각 배열의 요소의 개수를 나타내는 m, n 이 주어질 때 num1 과 num2 를 오름차순으로 정렬된 하나의 배열로 병합하는 문제이다.

 

문제의 조건으로는 최종 결과값은 함수에서 반환되지 않고, 배열 num1 내부에 저장되어야 한다. 

 

풀이

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

        Arrays.sort(nums1);
    }
}

 

 

 

시간복잡도

Arrays.sort() 메소드는 평균 시간복잡도가 O(n logn) 이다.

따라서 nums1 과 nums2 의 요소 개수를 합한 O((m+n) log(m+n)) 만큼의 시간 복잡도를 가지게 된다.

 

공간복잡도

O(1)