[leetcode] Find the Duplicate Number

·2024년 3월 24일
0

코딩

목록 보기
6/45

문제

  • 링크
  • n+1개의 정수가 들어있는 nums 배열이 주어진다. 배열 안에 있는 값의 범위는 [1, n] 이다. 배열 안에는 중복으로 들어간 수가 하나 있는데, 이를 찾아야 한다.
  • 제약 조건
    • 1 <= n <= 10^5
    • nums.length == n + 1
    • 1 <= nums[i] <= n

풀이

풀기 전

  • set 사용하면 간단히 풀릴 거 같다. 시간 복잡도와 공간 복잡도는 O(n)이다.

코드

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        
        HashSet<Integer> hs = new HashSet<>(n);
        for (Integer num : nums) {
            if (hs.contains(num))
                return num;
            hs.add(num);
        }
        return 0;
    }
}

푼 후

  • 이렇게 간단히 풀린다고..? 이상해서 다른 사람 코드를 보니 관련 알고리즘이 따로 있었다. 플로이드 순환 찾기 알고리즘, 또는 플로이드 토끼와 거북이 알고리즘으로 찾을 수 있었다. set을 따로 사용하지 않기 때문에 공간 복잡도를 O(1)로 줄일 수 있었다.
  • 주어진 배열을 연결 리스트로 생각했을 때, 순환되는 지점을 찾는 알고리즘이었다. 예를 들면 nums=[1, 3, 4, 2, 2]일 때, nums에 있는 값을 인덱스로 사용해서 연결 리스트로 표현할 수 있다. 연결 관계를 표현하면 아래와 같다.
    • Node(val=1, next=nums[1])
      -> Node(val=3, next=nums[3])
      -> Node(val=2, next=nums[2])
      -> Node(val=4, next=nums[4])
      -> Node(val=2, next=nums[2]) *순환 발생
    • 그 후에 알고리즘을 적용하면 된다. 알고리즘 설명은 생략한다.
profile
개발 일지

0개의 댓글