[LeetCode] 88. Merge Sorted Array

 가장 간단한 구현은 두 개의 array(list)를 첫 번째 array인 nums1으로 합친 후 정렬을 해주면 된다. 이 때는 시간 복잡도가 O (n log n) 이지만, Two Pointers (투 포인터)를 활용하면 O (n) 으로 두 개의 index를 각각 두고 각각의 element (요소)를 비교해가며 정렬된 array로 만들면 더 빠르게 구현이 가능하다.

 

1. 시간 복잡도: O (n log n)

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for i in range(n):
            nums1[m+i] = nums2[i]
        nums1.sort()

2. 시간 복잡도: O (n)

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i, j = 0, k = 0, l;
        
        l = nums1.length;
        int[] arr = new int[l], n1 = new int[m];
        
        for(i=0; i<m; i++)
            n1[i] = nums1[i];
        
        i = 0;
        while(i < m && j < n){
            if(n1[i] < nums2[j])
                arr[k++] = n1[i++];
            else
                arr[k++] = nums2[j++];
        }
        
        if(i < m){
            for(; i<m; i++){
                arr[k++] = n1[i];
            }
        }
        
        if(j < n){
            for(; j<n; j++){
                arr[k++] = nums2[j];
            }
        }

        System.arraycopy(arr, 0, nums1, 0, m+n);
    }
}