3. Merge Sorted Array

문제

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.

 

내가 생각한 방식 

통과 못함

while문에서 k만 0 이상인지 확인함 -> i, j가 0보다 작은 경우에도 계속 진행됨 -> 오류 발생

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    if (n != 0){
        // i는 nums1, j는 nums2의 요소가 있는 부분에 사용할 인덱스
        // k는 nums1 전체에 사용할 인덱스
        int i = m - 1;
        int j = n - 1;
        int k = nums1Size - 1;

        // 배열 끝에서부터 앞으로 가면서 두 배열 비교
        while(k >= 0){
            if (nums1[i] < nums2[j]){
                nums1[k--] = nums2[j--];
            } else {
                nums1[k--] = nums1[i--];
            }
        }
    }
}

 

해결 방법

https://leetcode.com/problems/merge-sorted-array/discuss/2360538/Easy-0-ms-100-(Fully-Explained)(Java-C%2B%2B-Python-JS-C-Python3)

while문에서 j가 0 이상인지 확인.

i, j 둘 중 하나가 0보다 작아지면 (한 배열은 할당을 마쳤다는 뜻) while 탈출.

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1

    while j >= 0:
        if i >=0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            k -= 1
            i -= 1

        else:
            nums1[k] = nums2[j]
            k -= 1
            j -= 1