aboutsummaryrefslogtreecommitdiff
path: root/find_duplicate_num.py
blob: f1d6170b25b8f02fd1aa508fb3c08b096b852427 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 287. Find the Duplicate Number

"""
given an integer array '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.
"""


class Solution(object):
    def findDuplicate(self, nums):
        for n in nums:
            idx = abs(n)
            if nums[idx] < 0:
                return idx
            nums[idx] = -nums[idx]
        return len(nums)


if __name__ == "__main__":
    obj = Solution()
    print(obj.findDuplicate([1, 3, 4, 2, 2]))  # expect: 2
    print(obj.findDuplicate([3, 1, 3, 4, 2]))  # expect: 3