[2024] day 86. Leetcode 442. Find All Duplicates in an Array

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 25일 (월)
Leetcode daily problem

287. Find the Duplicate Number

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

Problem

[1, n] 범위에 있는 정수 원소를 가진 nums가 주어질 때 각 정수는 한 번 혹은 두 번 나타난다. 이 때, 2번 이상 나타나는 정수 원소를 반환한다.

시간복잡도는 O(n) 시간에 실행되고 일정한 추가 공간만 사용하는 알고리즘을 작성한다.

Solution

array

배열의 중복 원소를 찾는 알고리즘은 주로 set을 이용해서 푸는데,

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        numSet = set()
        lst = []
        for num in nums:
            if num in numSet:
                lst.append(num)
            numSet.add(num)
        return lst

주로 이러한 방법으로 푸는데, 시간복잡도는 O(n), 공간복잡도도 O(n)로 해결할 수 있다.

그러나 해당 문제의 조건에서 'constant extra space' 라는 조건이 나와있다. 공간복잡도를 O(1)로 해결할 수 있는 다른 해결방법은 다음과 같다.

주어진 배열을 처음부터 끝까지 탐색하면서, 각 요소를 절대값으로 취한 값을 인덱스로 사용한다. 배열의 요소가 1부터 n까지의 숫자 중 하나이므로 중복된 숫자를 인덱스로 사용하면 해당 인덱스에 있는 값을 음수로 변경할 수 있다.
각 요소의 절대값으로 취한 값을 인덱스로 사용해서 해당 인덱스의 값을 음수로 변경한다. 음수로 변경된 값은 이미 방문한 숫자이므로,
해당 인덱스의 값이 음수이면 이를 중복된 숫자로 판단하고 해당 숫자를 결과 리스트에 추가한다. 탐색이 끝나면 결과 리스트를 반환한다.

Code

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans = []
        for num in nums:
            n = abs(num)
            if nums[n-1] < 0:
                ans.append(n)
            nums[n-1] = -nums[n-1]
        
        return ans 

Complexicity

시간 복잡도

주어진 배열을 처음부터 끝까지 탐색하므로 시간복잡도는 O(n)이다.

공간 복잡도

주어진 배열을 직접 수정하면서 탐색하므로 추가적인 공간은 결과 리스트 하나이다. 그러므로 O(k), k는 중복된 원소의 개수이다.