[알고리즘] leetcode - 88번

문제

• 문제
  정렬된 배열 nums1과 nums2가 주어지며, nums1은 충분한 공간을 할당받고 있습니다.
  nums1의 초기 크기는 m이고, nums2의 크기는 n입니다.
  두 배열을 합쳐서 nums1에 정렬된 형태로 저장해야 합니다.

• 조건

1. 0 <= m, n <= 200
2. 1 <= m + n <= 200
3. -10^9 <= nums1[i], nums2[i] <= 10^9

• 예시
  예제 1
  입력: nums1 = [1,2,3,-,-,-], m = 3, nums2 = [2,5,6], n = 3
  출력: nums1 = [1,2,2,3,5,6]
  설명: nums1의 처음 3개의 요소는 [1,2,3]이고, nums2는 [2,5,6]입니다. 두 배열을 합치면 [1,2,2,3,5,6]가 됩니다.

예제 2:
입력: nums1 = [1], m = 1, nums2 = [], n = 0
출력: nums1 = [1]
설명: nums2가 비어 있으므로 nums1은 변경되지 않습니다.

예제 3:
입력: nums1 = [ - ], m = 0, nums2 = [1], n = 1
출력: nums1 = [1]
설명: nums1이 비어 있고, nums2의 요소가 nums1으로 복사됩니다.

풀이 결과

해결

막혔던점 혹은 이유

sort함수를 사용하는게 편법인것 같아 맞는 풀이 인가 싶어서 머뭇거렸다.

배운점

.

런타임 가장빠른 답

class Solution {
  void merge(List<int> nums1, int m, List<int> nums2, int n) {
    int indexOfNums1 = m-1;
    int indexOfNums2 = n-1;
    int indexOfNums1Full = m+n-1;

    while(indexOfNums1 >= 0 && indexOfNums2 >=0) {
        if(nums1[indexOfNums1] > nums2[indexOfNums2]) {
            nums1[indexOfNums1Full] = nums1[indexOfNums1];
            indexOfNums1--;
        } else {
            nums1[indexOfNums1Full] = nums2[indexOfNums2];
            indexOfNums2--;
        }
        indexOfNums1Full--;
    }
    while(indexOfNums2 >= 0) {
        nums1[indexOfNums1Full] = nums2[indexOfNums2];
        indexOfNums1Full--;
        indexOfNums2--;
    }
  }
}

메모리 가장 적은 답

class Solution {
  void merge(List<int> nums1, int m, List<int> nums2, int n) {
    
   nums1.removeRange(m, nums1.length);
    nums2.removeRange(n,nums2.length);
     nums1.addAll(nums2);
     nums1.sort();
     
  }
}