Merge Sorted Array

문제

전제
내림차순으로 정렬된 두 개의 정수 배열 num1, nums2와 두 배열에 0을 제외한 정수의 개 수를 나타내는 두 정수 m, n이 있습니다.

nums1과 nums2은 하나의 배열로 병합되어 내림차순으로 정렬합니다.

최종적으로 정렬된 배열은 반환되는 함수는 아니지만 nums1배열안에 저장되어야합니다.
이를 수용하기 위해 nums1은 m+n의 길이를 갖는다.여기에서 첫번째 m은 병합되어야 하는 요소의 갯수를 나타내고 마지막 n의 요소들의 자리는 0으로 설정되며 무시한다.
nums2의 길이는 n이다.

예제1

입력: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
출력: [1,2,2,3,5,6]
설명 : 병합할 배열은 [1,2,3]과 [2,5,6]이다.
병합 결과는 [1,2,2,3,5,6]이다.

예제2

입력: nums1 = [1], m = 1, nums2 = [], n = 0
출력: [1]
설명 : 병합할 배열은 [1]과 []입니다.
병합 결과는 [1]입니다.

예제3

입력: nums1 = [0], m = 0, nums2 = [1], n = 1
출력: [1]
설명 : 병합할 배열은 []과 [1]입니다.
병합 결과는 [1]입니다.
NOTE m = 0의 의미는 nums1 배열에는 값이 존재하지 않는다는 말입니다.nums1의 0은 병합 결과 1이 들어오기 위해 존재합니다.

제약 조건

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

---

Solution

Arrays.sorted() 활용

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
 		
       int len1 = m + n;
       int len2 = n -1;
		
       for(int i = 0; i < len1; i++) {
        	if(nums1[i] == 0) {
                	if(len2 < 0 ) {
        				break;
        			}
        		nums1[i] = nums2[len2];
        		len2--; 
        		
        		}
        	}
        Arrays.sort(nums1);
    }
}

nums1[i]의 값이 0일 때 nums2의 마지막 요소부터 하나씩 넣어준 후 정렬해준다.

혹은

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
 
       int len = m + n;
		
		while(n > 0) {
			if(nums1[len-1] == 0) {
				nums1[len-1] = nums2[n-1];
				n--;
			}
			len--;
		}
        Arrays.sort(nums1);
    }
}

n의 개수 만큼만 반복하여 nums1의 뒷자리부터 nums2로 채워준다.

런타임이 가장 짧은 solution

		 int len1=m-1,len2=n-1,length=nums1.length-1;
		 
		 
	        while(len1>=0 && len2>=0){
	            	if(nums2[len2]>nums1[len1]){
	            		nums1[length--]=nums2[len2--];
	            	}else{
	            		nums1[length--]=nums1[len1--];
	                }
	        	}
	        	
	        while(len2>=0){
	            nums1[length--]=nums2[len2--];
	            }
	        
	        while(len1>=0) {
	            nums1[length--]=nums1[len1--];
	        }

nums1의 요소가 존재하는 배열과 nums2의 배열의 값을 비교하여 마지막 요소 부터 채워 넣으며 정렬한다.