[C++] LeetCode : Merge Sorted Array

Question

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 및 nums2와 각각 nums1 및 nums2의 요소 수를 나타내는 두 개의 정수 m 및 n이 제공됩니다.

nums1과 nums2를 비내림차순으로 정렬된 단일 배열로 병합합니다.

최종 정렬된 배열은 함수에 의해 반환되지 않고 대신 배열 nums1 내에 저장되어야 합니다. 이를 수용하기 위해 nums1의 길이는 m + n입니다. 여기서 처음 m개 요소는 병합해야 하는 요소를 나타내고 마지막 n개 요소는 0으로 설정되어 무시되어야 합니다. nums2의 길이는 n입니다.

 

제약사항

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• O(m + n)

문제를 풀 때 고려한 사항

• 최대한 BCR 이내로 풀어볼 수 있게 한다.
• 각각 m과 n 크기의 두 개의 정렬된 배열 nums1과 nums2가 제공됩니다. 이 두 배열을 하나의 정렬된 배열로 병합해야 하며 결과는 nums1에 저장되어야 합니다. nums1의 크기는 m+n이므로 이 추가 공간을 사용하여 병합된 배열을 저장할 수 있습니다. 배열의 끝부터 반복하여 nums1의 끝에 더 큰 요소를 배치할 수 있습니다.

---

Solution1 : Using STL

nums2를 탐색하고 인덱스 m부터 시작하여 nums1의 끝에 해당 요소를 추가합니다.
sort() 함수를 사용하여 전체 nums1 배열을 정렬합니다.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int j = 0, i = m; j<n; j++){
            nums1[i] = nums2[j];
            i++;
        }
        sort(nums1.begin(),nums1.end());
    }
};

• Time complexity : O((m + n)log(m + n)) 
• Space Complexity : O(1) 

Solution2 : Two Pointer

1. 포인터 i와 j를 각각 m-1과 n-1로 초기화합니다.
2. 또 다른 포인터인 k를 m+n-1로 초기화합니다. 이 포인터는 nums1 배열에서 더 큰 요소를 배치할 위치를 추적하는 데 사용됩니다.
3. 배열 i와 j의 끝에서부터 시작하여 해당 위치의 요소를 비교합니다.
4. nums1의 더 큰 요소를 k 위치에 배치하고, 이에 따라 해당 포인터 i 또는 j를 감소시킵니다.
5. nums2의 모든 요소를 반복할 때까지 이 작업을 반복합니다.
6. 만약 nums1에 아직 요소가 남아 있다면, 해당 요소는 이미 올바른 위치에 있으므로 아무 작업도 필요하지 않습니다.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
};

• Time complexity : O(m + n) 
• Space Complexity : O(1) 

 

출처 : https://leetcode.com/problems/merge-sorted-array/solutions/3436053/beats-100-best-c-java-python-and-javascript-solution-two-pointer-stl/