LeetCode 26 Remove Duplicates from Sorted Array

nayu1105·2023년 8월 23일

leetcode 알고리즘

LeetCode

목록 보기

1/28

LeetCode 26 Remove Duplicates from Sorted Array 풀러가기

문제

오름차순 정렬된 nums가 있다.
여기서 중복된 숫자들을 삭제하고, 중복제거하고 남은 숫자의 갯수, k를 리턴하면 된다.

예를 들어 {1,1,2}라는 배열을 주면 {1,2,_} 배열로 만들고, 2를 리턴하면 된다.

문제 분석

첫번째 시도 (소요 시간 3분)

nums 배열을 for문으로 전체 순회하며 중복제거된 nums 배열의 마지막값인 before과 비교해서, 같다면 index 변수를 증가시키지 않고, 다르다면 nums 배열 index 번 째에 넣고, index를 증가시키는 전략을 짰다.

시간복잡도는 O(n) 인데, 전체 nums 배열을 비교할 수 밖에 없으니 이게 최선이라고 생각했다.

코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 1;
        int before = nums[0];
        for(int i=1; i<nums.length; i++){
            if(nums[i]==before)continue;
            else{
                nums[index]=nums[i];
                before=nums[i];
                index++;
            }
        }

        return index;
    }
}

결과 : 성공

Runtime

Memory

시간은 상위 98퍼, 메모리는 상위 97퍼이니 꽤 괜찮다고 생각했다.

두번째 시도

before이라는 변수말고 nums[index-1]로 짜는 새로 짜보았다.

코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 1;
        for(int i=1; i<nums.length; i++){
            if(nums[i]==nums[index-1])continue;
            else{
                nums[index]=nums[i];
                index++;
            }
        }

        return index;
    }
}