287. Find the Duplicate Number
287. Find the Duplicate Number
要求时间复杂度小于O(n2)
空间复杂度O(1)
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
while i < len(nums):
if nums[i] == i+1:
i += 1
else:
if nums[nums[i]-1] == nums[i]:
return nums[i]
else:
a = nums[nums[i]-1]
nums[nums[i]-1] = nums[i]
nums[i] = a
网友评论