Leetcode - 442. Find All Duplicates in an Array

이번에는 배열 안에 중복된 숫자를 찾아 내는 로직입니다.
숫자는 중복 안된 숫자들과 한번만 중복된 숫자들이 있습니다. (두번 이상 중복된 숫자는 없습니다.)

총 4가지 방법이 있는데 그 중 첫번째는 아래 스크립트 입니다.

 

한 줄 한 줄 살펴보면 아래와 같습니다.

 

class Solution { // 클래스 이름은 Solution 입니다.

    public List<Integer> findDuplicates(int[] nums) { // 메소드 이름은 findDuplicates이고 입력값은 nums 라는 integer 배열이고 리턴값은 Integer 타입 리스트 입니다.

        List<Integer> ans = new ArrayList<>(); // 리턴 할 리스트를 ArrayList 로 선언합니다. 변수 이름은 ans 

        for(int i = 0; i < nums.length; i++) { //일단 입력된 배열 내의 값의 개수 만큼 for 문을 돌립니다.

            for(int j = i+1; j < nums.length; j++) { // 첫번째 값과 그 나머지 값을 비교해야 하니까 총 개수 - 1 만큼 for문을 다시 돌려 줍니다.

                if(nums[j] == nums[i]) { // 만약에 같은 숫자가 나오면서 이 if 문을 실행 합니다.

                    ans.add(nums[i]); // ans에 해당 숫자를 넣습니다.

                    break; // 나머지는 비교하지 않고 그냥 나가서 I++이 적용 되서 그 다음 숫자를 가지고 비교 합니다.

                }

            }

        } // 이렇게 되면 중복된 숫자들만 ans에 들어가게 됩니다.

        

        return ans; // 구해진 값을 리턴 합니다.

    }

}

 

이 예제는 아주 베이식한 방법인 것 같습니다.

다른 방법은 어떤 것이 있을 까요?

 

class Solution {

    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> ans = new ArrayList<>();

        

        Arrays.sort(nums); // 입력 값을 정렬 합니다. 

        

        for(int i = 1; i < nums.length; i++) {

            if(nums[i] == nums[i - 1]) { // 정렬이 돼 있고 중복이 안 됐거나 한번만 중복이 된 경우만 존재 하므로 바로 이전 숫자와 비교해서 같으면 이 if 문을 실행 합니다.

                ans.add(nums[i]);

                i++;

            }

        }

        return ans;

    }

}

 

이 코드는 이 배열의 값들이 중복이 안 됐거나 한번만 중복 된 값만 있는 정수 들이기 때문에 가능합니다.

순서대로 정렬해서 바로 이전 숫자와 비교만 하면 됩니다.

 

그 다음 방법으로는 

 

이것은 HashSet을 사용한 예제 입니다.

HashSet은 중복을 허용하지 않습니다. 

그래서 이 HashSet의 contains라는 메소드 를 사용해서 해당 값이 있으면 ans에 넣고 없으면 seen이라는 HashSet에 넣어서 나중에 ans만 리턴 하는 로직 입니다.

 

class Solution {

    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> ans = new ArrayList<>();

        Set <Integer> seen = new HashSet<>();

        

        for(int num : nums) {

            if(seen.contains(num)) { // HashSet 내에 이미 같은 숫자가 있으면 if 문을 실행합니다.

                ans.add(num);

            }else{ // HashSet내에 같은 숫자가 없으면 이 else 문을 실행합니다.

                seen.add(num);

            }

        }

        return ans;

    }

}

 

 

마지막 예제는 잘 이해가 안 되네요.  

나중에 시간 날 때 분석해 봐야 겠습니다.

 

class Solution {

    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> ans = new ArrayList<>();

        

        for(int num : nums) {

            nums[Math.abs(num) - 1] *= -1;

        }

        

        for(int num : nums) {

            if (nums[Math.abs(num) - 1] > 0) {

                ans.add(Math.abs(num));

                nums[Math.abs(num) - 1] *= -1;

            }

        }

        return ans;

    }

}