leetcode 287. Find the Duplicate Number 풀이

문제 : n+1 길이의 [1, n] 사이의 정수를 포함하는 list에서 중복되는 숫자 하나를 반환하라 (하나만 존재함)

Follow up :

 

1. Nums를 변환하지 말 것

2. O(1) 만큼의 메모리만 사용하여 해결할 것

3. O(n^2) 이하의 시간 복잡도를 가질 

아이디어 : Follow up을 모두 충족하는 풀이를 생각했지만 어려웠다. 다른 사람의 코드를 보고 이해한 내용을 아래에 기술할 것이다.

 

코드 :

 

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        d = dict()
        for num in nums:
            if num in d:
                d[num] += 1
            else:
                d[num] = 1
        for key in d:
            if d[key] > 1:
                return key

학습 포인트 : dictionary를 사용하여 간단하게 풀었지만 follow up은 충족시키지 못했다.

 

출처 : leetcode.com/problems/find-the-duplicate-number/