[Leetcode] 88. Merge Sorted Array 문제풀이

https://leetcode.com/problems/merge-sorted-array/

Merge Sorted Array - LeetCode

 

문제 내용

2개의 배열을 merge sort로 합치기

 

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.

 

문제 풀이

배열 하나를 선언해서 비교하면서 하나씩 삽입하면 된다.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums(nums1.begin(), nums1.begin()+m);
        
        for (int i = 0, i1 = 0, i2 = 0; i < nums1.size(); ++i) {
            if (i1 == m) {
                nums1[i] = nums2[i2++];
            } else if (i2 == n) {
                nums1[i] = nums[i1++];
            } else {
                if (nums[i1] < nums2[i2]) {
                    nums1[i] = nums[i1++];
                } else {
                    nums1[i] = nums2[i2++];
                }
            }
        }
    }
};

 

추가적인 메모리를 사용하지 않고도 가능하다.

처음부터 삽입하면 index가 매우 꼬인다;;

그래서 마지막 배열부터 하나씩 삽입하면 된다.

마지막 배열에는 nums1이 0으로 empty 값으로 되어 있기 때문이다.