[LeetCode] Find All Duplicates in an Array

 

 

 

 

문제

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/?envType=daily-question&envId=2024-03-25

 

 

파라미터로 주어진 nums에 중복된 수가 있으면 그 수를 찾아 return 하라는 간단한 문제입니다.

 

 

 

해석

 

3가지 방법으로 풀어보겠습니다.

 

1. 1 ~ N 까지의 체크할 수 있는 공간을 만들어두기

 

이 경우엔, 1 ~ N을 리스트로 만들어 1의 값으로 만들어 두고, nums를 돌며 나오는 값을 리스트에서 -1 해준다.

arr = [1] * (N+1)
for i in nums:
	arr[i] -= 1
for i in nums:
    if arr[i] < 0:
        ans.append(i)
        
return ans

 

 

다만 이 방법의 경우 N이 크다면 초기에 설정해줘야 하는 arr의 크기가 너무 커질 수 있어 낭비적일 수 있다.

 

 

2. 그렇다면  arr를 리스트 말고 set으로 만들자

nums를 돌며 나오는 값이 이미 set안에 있다면, 답의 값이 되는 것이다.

check = set()
ans = set()
for i in nums:
	if i in check:
    	ans.add(i)
    else:
    	check.add(i)

ans = list(ans)
ans.sort()
return ans

 

 

이 방법은 1번의 공간 낭비 문제에서 조금은 벗어날 수 있지만, 여전히 최악의 경우 O(n)이 걸리게 된다.

 

그렇게 해서, 마지막 방법

 

 

3. nums의 모든 값이 양수임으로, 처음부터 체크해가며 num의 인덱스의 값을 -로 바꿔둔다.

 

이렇게 하게 되면, nums를 순회하며 가다가 - 인 값이 나온다면,

이 값이 이미 체크가 된 값으로 정답인 인덱스가 된다는 논리이다.

 

하지만, 이 방법이 논리적이려면

모든 nums의 원소들이 양수여야하고,

원소들의 값이 nums의 길이보다 작은 값이어야 한다.

라는 제약 조건이 필요하다

 

ans = []

for i in range(len(nums)):
    if nums[i] < 0:
    	  ans.append(i+1)
    else:
	nums[nums[i]] = abs(nums[nums[i]]) * -1

return ans

 

이렇게 구현을 하게 되면, 추가로 써야 하는 공간은 없어지게 되고, nums 한번의 순회로 답을 구할 수 있게 된다.

 

 

끗!