[Easy] LeetCode - no.26 Remove Duplicates from Sorted Array : Java

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

nums라는 배열에서 중복되는 숫자를 지운 후, 남은 nums의 값의 개수를 return할 것

이 때 nums의 0번째 index부터 중복되지 않은 숫자들이 나열되어 있어야 함

Example 1:
Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

 

 

 

 

풀이

import java.util.*;

class Solution {
    public int removeDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();

        for (int n : nums) {
            if (list.indexOf(n) < 0) {
                list.add(n);
            }
        }

        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }

        return list.size();
    }
}

 

• ArrayList 사용
• list.indexOf()가 0 미만인 수라면 (list에 존재하지 않는 수라면) add
• list.size()를 리턴
• 시간복잡도 : O(N*M)

 

더 좋은 방법에 대한 고민

1. list.indexOf()로 비교하는 것이 아닌 list.contains() 사용

import java.util.*;

class Solution {
    public int removeDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();

        for (int n : nums) {
            if (!list.contains(n)) {
                list.add(n);
            }
        }

        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }

        return list.size();
    }
}

 

 

2. List를 사용하지 않고 int 배열 내에서 처리

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

• 이해는 됐지만 한 번에 와닿지 않는 것 같은 코드...