[leetcode] 88. Merge Sorted Array

in-place로 작성해야하니 컬렉션을 복재해서 코딩하면 안됨. 변환값이 없기도 하고...

 

Time Complexity: O(m+n)

Space Complexity: O(1) 

The function uses a fixed amount of extra space regardless of the input size. Only a few integer variables are used for index tracking, so the space complexity is

 

/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {

    let i = m - 1;  // Pointer for the end of the actual elements in nums1
    let j = n - 1;  // Pointer for the end of nums2
    let k = m + n - 1;  // Pointer for the end of nums1
	console.log(i, j, k) // 2, 2, 5
    
    // Merge in reverse order
    while (i >= 0 && j >= 0) {
        console.log(nums1[i], nums2[j])
        // 3, 6 -> [1, 2, 3, 0, 0, 5] | j === 1 
        // 3, 3 -> [1, 2, 3, 0, 3, 5] | j === 0
        // 3, 2 -> [1, 2, 3, 3, 3, 5] | i === 1
        // 2, 2 -> [1, 2, 2, 3, 3, 5] | j === -1
        if (nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }

    // If nums2 is not exhausted
    while (j >= 0) {
        nums1[k] = nums2[j];
        j--;
        k--;
    }
};

const nums1 = [1,2,3,0,0,0]
const numb2 = [2,3,6]

merge(nums1, 3, numb2, 3)
console.log(nums1) // [1, 2, 2, 3, 3, 6]