[leetcode] Find All Duplicates in an Array

문제

• 링크
• 길이가 n인 nums 배열이 주어진다. 들어있는 값의 범위는 [1, n]이고, 각 값들은 nums 안에 한 번 또는 두 번 들어있다. 두 번 들어간 값들을 찾아야한다.
• 제약 조건
  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n

풀이

풀기 전

• 시간 복잡도가 O(n)이고 공간 복잡도가 O(1)이어야 한다는 제약이 있다. set으로 풀면 간단하겠지만 공간 복잡도에서 걸린다.
• 이전 문제에서 썼던 플로이드 순환 찾기 알고리즘을 써야 하나? 중복으로 들어간 값이 여러개이기 때문에 적절하지 않아 보였다. 단순히 방문했던 곳을 체크하면 될거 같은데 아이디어가 영 떠오르지 않았다. 그래서 다른 사람 코드를 참고했다.

코드

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        ArrayList<Integer> ret = new ArrayList<>();
        
        // nums를 순회한다.
        for (int i=0; i<nums.length; i++) {
            int num = Math.abs(nums[i]);
            
            // 값의 범위가 [1, n]이기 때문에 값-1을 인덱스로 사용할 수 있다.
            // 값-1을 인덱스로 사용한 곳이 음수라는 건 이미 방문했다는 뜻이므로 중복 값이라는 걸 알 수 있다.
            if (nums[num-1] < 0)
                ret.add(num);
                
            // 값-1을 인덱스로 사용하여 방문 표시를 해준다.
            nums[num-1] *= -1;
        }

        return ret;
    }
}

푼 후

• 이것저것 고민하다가 풀이가 안 떠올라서, 이전 문제처럼 알고리즘 쓰는 거겠거니 하고 다른 사람 코드를 봤는데 아니었다ㅠ
• 방문했던 곳을 체크한다는 생각까진 했는데, 핀트를 조금 다르게 생각했다. 만약 2가 중복 값이라면, 값이 2인 곳에다가 방문 체크를 한다고만 생각했다. 그런데 2를 인덱스로 써서 조회하는 곳에 방문 체크를 하면 되는 거였다. 조금 더 고민해볼 걸 그랬다.