LeetCode 287. Find the Duplicate Number

Posted on | In |
Words count in article: 167 | Reading time ≈ 1

题目

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

1
2
Input: [1,3,4,2,2]
Output: 2

Example 2:

1
2
Input: [3,1,3,4,2]
Output: 3

Note:

  • You must not modify the array (assume the array is read only).
  • You must use only constant, O(1) extra space.
  • Your runtime complexity should be less than O(n^2).
  • There is only one duplicate number in the array, but it could be repeated more than once.

思路

通过重复元素的索引找到重复元素。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
	        if nums[abs(nums[i])]>0:
		        nums[abs(nums[i])]=-nums[abs(nums[i])]
	        else:
		        return abs(nums[i])