LeetCode(Contains Duplicate)

금일 풀어본 문제는 Contains Duplicate라는 알고리즘이다.

 

Url : https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/578/

 

문제에서 물어본 내용은 배열에 같은 값이 최소 2개가 있으면 True, 아니면 False로 반환하라고 했다.

 

---

 

첫번째 문제 풀이 방법

1. nums[i]의 최소값과 최대값만큼 (약 10억)개의 boolean 리스트 생성

2. nums.length를 전체돌면서 한번 방문한 곳은 true로 변경

3. 다시 방문했을때 해당 index가 true로 되어있으면 두번째 방문이므로 리스트에 해당 숫자가 2개임을 파악가능

 

실패 : out of memory

사유 : 10억개의 인자를 가진 배열을 생성할때 아웃 오브 메모리 발생함

 

시간 복잡도: O(n), n은 nums.length

공간 복잡도: O(10^9), lstNum 배열의 크기

public boolean containsDuplicate(int[] nums) {
        boolean answer = false;
        boolean[] lstNum = new boolean[1000000001];

        for (int i=0; i < nums.length; i++){
            if ( lstNum[nums[i]]) {
                answer = true;
                break;
            }
            lstNum[nums[i]] = true;
        }

        return  answer;
    }

 

 

두번째 문제 풀이 방법

1. 주어진 배열을 정렬함.

2. 배열을 돌면서 전값과 다음값이 같으면 2개 이상 배열에 포함됨을 알 수 있음

 

시간 복잡도 : O(nlogn)

공간 복잡도 : O(1)

public boolean containsDuplicate2(int[] nums) {
        boolean answer = false;

        Arrays.sort(nums);

        for (int i=0; i < nums.length - 1; i++){
            if ( nums[i] == nums[i+1]) {
                answer = true;
                break;
            }
        }

        return  answer;
    }

 

 

세번째 문제 풀이 방법

 

1. hashset을 만듬

2. 주어진 배열을 for문을 돌면서 hashset에 중복된 값이 있는지 확인후에 없으면 hashset 객체에 dd

 

시간 복잡도 : O(n)

공간 복잡도 : O(n)

public boolean containsDuplicate(int[] nums) {
        boolean answer = false;

        HashSet<Integer> checkNum = new HashSet<>();

        for (int num : nums){
            if (checkNum.contains(num)){
                return true;
            }
            checkNum.add(num);

        }

        return  answer;
    }

 

 

2번 방법은 공간복잡도를 가장 줄일수 있으며, 3번 방법은 시간 복잡도를 줄일 수 잇음