기억하고싶은것들

You are given two integer arrays nums1 and nums2, sorted in nondecreasing 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.

두 개의 integer 오름차순 배열 nums1, nums2과 m, n integer를 받는다.

m, n은 각 배열이 가지고 있는 element의 개수이다.

이 두 배열을 하나의 오름차순 배열로 통합하여라.

단, 리턴되는 배열은 새로 정의된 배열이 아닌 nums1 배열이어야 한다.

nums1 배열은 크기가 m+n이다. 

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

정렬된 두 개의 배열을 merge 해야 한다.

단, 새로운 배열을 생성하여 merge 하는 것이 아닌 주어진 배열에서 merge가 이루어져야 한다.

주어진 배열의 마지막 element들을 point 하고 그중에 큰 값을 nums1 배열에 입력하는 형식으로 문제를 해결해 보자.

해당 순회를 마무리하는 조건으로는 각 배열의 pointer들이 0보다 작아진 경우이다. 

후에 만약 nums2의 pointer가 첫 index까지 순회를 하지 못한 경우에는 해당 값들을 nums1에 입력해주면 모든 배열을 순회한 것이다. 

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        int nums1Idx = m - 1;
        int nums2Idx = n - 1;

        int point = nums1.length - 1;

        while (nums1Idx >= 0 && nums2Idx >= 0) {

            if (nums1[nums1Idx] >= nums2[nums2Idx]) {
                nums1[point] = nums1[nums1Idx];
                point--;
                nums1Idx--;
            } else {
                nums1[point] = nums2[nums2Idx];
                point--;
                nums2Idx--;
            }
        }

        if (nums2Idx >= 0) {
            while (nums2Idx >= 0) {
                nums1[point] = nums2[nums2Idx];
                point--;
                nums2Idx--;
            }
        }

    }

시간 복잡도는 각 배열을 모두 순회하므로 O( M + N )이다.

문제 출처

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