[Leetcode]287 : Find the Duplicate Number

jojo lee
Jul 22, 2021


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.


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