88. Merge Sorted Array

다음과 같은 문제는 두 개의 졍렬된 배열을 하나의 정렬된 배열로 합치는 작업을 수행하는 것입니다. 문제를 풀기 위한 접근 방법은 다음과 같습니다.

 

1. 두 배열의 끝부터 시작합니다. 즉, 배열의 가장 큰 값을 가리키는 포인터를 각각 두 배열에 대해 설정합니다.

2. 한 배열에서 다른 배열로 원소를 복사하면서 합칩니다. 큰 값을 가진 원소를 결과 배열의 끝에 넣어주면서 포인터를 이동합니다.

3. 만약 두 배열 중 하나의 배열을 모두 처리하면, 남은 원소는 이미 결과 배열의 올바른 위치에 있으므로 추가 작업이 필요하지 않습니다.

 

이 솔류션의 시간복잡도는 O(m+n)

병합을 위해 상수 공간을 사용합니다. O(1)

 

Java로 푸는 방법:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1; // Pointer for nums1
        int j = n - 1; // Pointer for nums2
        int k = m + n - 1; // Pointer for the merged array

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }

        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
    }
}

 

Python로 푸는 방법:

def merge(nums1, m, nums2, n):
    # Initialize two pointers, one for each array, starting from the ends.
    i = m - 1  # Pointer for nums1
    j = n - 1  # Pointer for nums2
    k = m + n - 1  # Pointer for the merged array
    
    # Merge nums1 and nums2 from the end to the beginning
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    # If there are remaining elements in nums2, copy them into nums1
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1