[LeetCode] 442. Find All Duplicates in an Array - 해시셋(HashSet) + 아이디어(Idea) JAVA

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

코드설명

해시셋(HashSet) + 아이디어(Idea) 을 활용합니다.

 

가장 떠오르기 쉬운점은, 해시맵이나 해시셋을 활용하여 2개 빈도의 숫자를 구할 수 있습니다.

하지만, 문제에서 상수 공간복잡도를 명시했으니, int[] nums를 그대로 사용하여 처리합니다.

나온 숫자에 음수를 곱함으로써 한번 처리했다는 것을 보여주고, Math.abs로 기존 숫자는 그대로 가져올 수 있습니다.

코드

정답코드2입니다. 공간복잡도를 O(1)로 처리하여 효율적입니다.

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        for(int i=0; i<n; i++){
            int x = Math.abs(nums[i]);
            if(nums[x - 1] < 0){
                ans.add(x);
            }
            nums[x - 1] *= -1;
        }
        return ans;
    }
}

HashSet을 활용한 코드입니다.

uses only constant auxiliary space, 라는 조건이 존재하지만, 공간복잡도를 상수복잡도로 처리하지 못한 코드입니다.

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        HashSet<Integer> hashset = new HashSet<>();
        List<Integer> arr = new ArrayList<Integer>();
        for(int i=0; i<nums.length; i++){
            if(hashset.contains(nums[i]) == true){
                arr.add(nums[i]);   
            }else {
                hashset.add(nums[i]);
            }
        }   
        return arr;
    }
}