문제
- 링크
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])
*순환 발생
- 그 후에 알고리즘을 적용하면 된다. 알고리즘 설명은 생략한다.