[leetcode 88] Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example:

Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]

 

Constraints:

• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1.length == m + n
• nums2.length == n

문제 풀이:

난이도 : 쉬움

어렵게 생각했는데 새로운 배열을 만들어서 정렬시킨 후에 다시 nums1에 반영하면 되었다.

정렬 시 사용한 알고리즘은 머지 소트에서 쓰이는 투포인터

 

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
        vector<int> tmp(n+m, 0);
        
        int i = 0;
        int left = 0, right = 0;
        
        while(left <m &&  right <n){
            if(nums1[left] < nums2[right]){
                tmp[i] = nums1[left];
                left++;
            }else {
                tmp[i] = nums2[right];
                right++;
            }
            i++;
        }
        
        while(left<m){
            tmp[i++] = nums1[left++];
        }
        
        while(right<n){
            tmp[i++] = nums2[right++];
        }
        
        for(int i=0; i<n+m; i++){
            nums1[i] = tmp[i];
        }
    }
};