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