leetcode

Find the Duplicate Number

Find the Duplicate Number

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = {}
        for i in nums:
            if i in d:
                return i
            else:
                d[i] = 1

O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 0
        high = len(nums) - 1
        mid = (high + low) / 2
        while high - low > 1:
            count = 0
            for x in nums:
                if mid < x <= high:
                    count += 1
            if count > high - mid:
                low = mid
            else:
                high = mid
            mid = (high + low) / 2
        return high

test code

1
2
In [179]: s = Solution(); t = s.findDuplicate([5,4,7,8,1,2,3,1,1,9]); print t
1

leet code