문제

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.

구현 전 예상 풀이

투 포인터로 풀이를 진행할 것이다.
nums1 배열의 m 개의 데이터를 새로운 배열에 nums3에 복사한다.
nums2 와 nums3의 index를 비교한 후 크기가 작은 배열의 값을 nums1로 복사한다. 그리고 index를 증가시킨다.
nums2와 nums3중에 값이 남은 배열의 값들을 nums1로 복사한다.

의사 코드

nums3 = copy(nums1, 0, m)
im = 0
in = 0
for(i = 0; i < m + n; i++)
	if(im >= m)
    	nums1[i] = nums2[in]
        in++
    else if(in >= n)
    	nums1[i] = nums3[im]
        im++
	else if(nums3[im] < nums2[in])
    	nums1[i] = nums3[im]
        im++
    else
    	nums1[i] = nums2[in]
        in++
	

구현 코드

int[] nums3 = Arrays.copyOf(nums1, m);

int im = 0;
int in = 0;

for (int i = 0; i < m + n; i++) {
    if (im >= m) {
        nums1[i] = nums2[in];
        in++;
    } else if (in >= n) {
        nums1[i] = nums3[im];
        im++;
    } else if (nums3[im] < nums2[in]) {
        nums1[i] = nums3[im];
        im++;
    }else {
        nums1[i] = nums2[in];
        in++;
    }
}

결과

예전 풀이

결과에서 볼 수 있듯이 사실 이 문제는 예전에 한 번 풀었었다.
오늘 풀이와 예전 풀이는 비슷하다. 그러나 오늘 코드가 더 깔끔하다.

int[] nums = new int[m];

for(int i = 0; i < m; i++)
    nums[i] = nums1[i];

int i = 0;
int a = 0;
int b = 0;

while(a < m && b < n){
    if(nums[a] < nums2[b]){
        nums1[i] = nums[a];
        a++;
    }else{
        nums1[i] = nums2[b];
        b++;
    }
    i++;
}
while(a < m){
    nums1[i] = nums[a];
    i++;
    a++;
}
while(b < n){
    nums1[i] = nums2[b];
    i++;
    b++;
}

다른 사람 풀이

마지막 인덱스부터 크기를 비교해가면 배열을 복사하지 않아도 된다.

//variables to work as pointers
int i = m - 1; // will point at m-1 index of nums1 array
int j = n - 1; // will point at n-1 index of nums2 array
int k = nums1.length - 1; //will point at the last position of the nums1 array

// Now traversing the nums2 array
while (j >= 0) {
    // If element at i index of nums1 > element at j index of nums2
    // then it is largest among two arrays and will be stored at k position of nums1
    // using i>=0 to make sure we have elements to compare in nums1 array
    if (i >= 0 && nums1[i] > nums2[j]) {
        nums1[k] = nums1[i];
        k--;
        i--; //updating pointer for further comparisons
    } else {
        // element at j index of nums2 array is greater than the element at i index of nums1 array 
        // or there is no element left to compare with the nums1 array 
        // and we just have to push the elements of nums2 array in the nums1 array.
        nums1[k] = nums2[j];
        k--;
        j--; //updating pointer for further comparisons
    }
}

88. Merge Sorted Array
다른 사람 풀이 링크