88. Merge Sorted Array c++ 문제

 

88. 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.

감소하지 않는 순서로 정렬된 두 개의
정수 배열 nums1 및 nums2와 각각 nums1 및 nums2의 
요소 수를 나타내는 두 개의 정수 m 및 n이 제공됩니다.

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

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

 

 

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

 

Constraints:

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

 

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

O(m + n) 시간에 실행되는 알고리즘을 생각해낼 수 있습니까?

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int num1Idx = m-1;
        int num2Idx = n-1;
        int wIdx = nums1.size()-1;
        
        while(0 <= num1Idx  && 0 <= num2Idx)
        {
            int num1 = nums1[num1Idx];
            int num2 = nums2[num2Idx];
            
            if(num1 < num2)
            {
                nums1[wIdx] = num2;
                num2Idx--;
                wIdx--;
            }
            else
            {
                nums1[wIdx] = num1;
                num1Idx--;
                wIdx--;
            }
        }
        while(0 <= num2Idx)
        {
            nums1[wIdx] = nums2[num2Idx];
            num2Idx--;
            wIdx--;
        }
        
    }
};

문제를 풀면서 느낀점은 문제가 좀 난해했다 보기에는 쉬워 보였는데

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

을 신경써서 idx를 옴겨주며 풀어야 했다.

 

그리고 두번째 while문

while(0 <= num2Idx)
        {
            nums1[wIdx] = nums2[num2Idx];
            num2Idx--;
            wIdx--;
        }

 

이와같은 input값이 들어 오면

오류가 나기에 써주었다. 

 

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문