[리트코드] 88.Merge Sort Array / 27.Remove Element

[zzu-yaaa]

4f24581

88.Merge Sort Array

성공 (7m 48s)

카테고리

배열, 정렬

접근

1. 정답을 저장하기 위한 배열 정의
2. 정의한 배열에 주어진 num1, num2의 값 저장
3. 배열 정렬
4. num1 배열로 값 옮기기

분석

O((m+n)log(m+n))

• Collections.sort()의 시간 복잡도는 O(NlogN)

회고

시간복잡도 최적화 가능 O(m+n)

    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int i = m-1;
            int j = n-1;
            int k = m+n-1;
    
            while(i >= 0 && j >= 0){
                if(nums1[i] > nums2[j]){
                    nums1[k--] = nums1[i--];
                }
                else{
                    nums1[k--] = nums2[j--];
                }
            }
    
            while(j >= 0){
                nums1[k--] = nums2[j--];
            }
        }
    }

1. 주어진 두 배열을 비교하며 큰 수부터 뒤에서 저장
2. num2 배열이 남아있는 경우 추가로 저장 (num1은 기존 배열이기 때문에 추가 저장 필요 x)

27.Remove Element

성공 (8m 33s)

카테고리

배열

접근

1. k 정의 → 인덱스 위치 및 전체 요소 개수 저장용
2. 주어진 배열을 돌면서 val과 일치하지 않는 경우에만 인덱스 값 갱신 & 값 저장

분석

O(N)이나, N이 최대 100이기 때문에 매우 빠름

회고

정해와 똑같은 풀이 굳👍