[Leetcode]287 : Find the Duplicate Number

Link : https://leetcode.com/problems/find-the-duplicate-number/

Problem :
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

圖來自leetcode

Thoughts :
1. 用collections.Counter來計算每個數字出現的次數。
2. 如果 count > 1，直接 return。

Solution :

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        count = collections.Counter(nums)
        for i,j in count.items():
            if j > 1:
                return i

time complexity, space complexity