[Algorithm] 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.

Example:
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.

 

주어진 조건을 정리하면,

결과는 num1에 저장되어야 하며 num1의 길이는 m+n이고 처음 m개의 배열만큼은 num1에서 그리고 n개의 배열 만큼은  num2에서 가져와 두개의 배열을 병합한 다음 정렬를 하는 문제입니다.

 

Solution :

일단 결과는 num1에 m개 만큼 배열을 먼저 생각하면 그냥 인덱스를 m까지 그대로 가지고 num2의 처음 인덱스에서 n까지의 배열을 더한 후 정렬을 하면 됩니다.

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0;i<n;i++){
            // 인덱스 m + 1 부터 num2 n개 만큼 배열을 추가해 줍니다.
            nums1[m+i] = nums2[i];
        }
        // sort함수를 이용하여 정렬을 합니다.
        Array.Sort(nums1);
    }
}

 

If you think about the array as many as m in num1, you just have to keep the index up to m, add the array from the first index of num2 to n, and sort it out.