[Easy] LeetCode - no.88 Merge Sorted Array : Java

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

 

 

문제

오름차순으로 정렬되어 있는 nums1과 nums2라는 int 배열을 하나의 오름차순으로 정렬된 int 배열로 합칠 것

(nums1에 값을 저장할 것)

 

 

 

풀이

import java.util.*;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            list.add(nums1[i]);
        }

        for (int i = 0; i < n; i++) {
            list.add(nums2[i]);
        }

        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            nums1[i] = list.get(i);
        }
    }
}

 

• ArrayList와 Colletions.sort() 사용
• ArrayList에 nums1과 nums2의 값을 전부 add한 후 Collections.sort() -> nums1 배열로 다시 옮김
• 시간복잡도 : O(N log N)

 

더 좋은 방법에 대한 고민

• nums1의 끝에 nums2를 합친 후 Arrays.sort() 사용

import java.util.*;

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

        Arrays.sort(nums1);
    }
}