[LeetCode] 287. Find the Duplicate Number

 Problem : https://leetcode.com/problems/find-the-duplicate-number/

Put number n back to its origin position Nums[n-1].

The first number n which Nums[n-1] != n is the duplicate number.

Time Complexity = O ( N )

Space Complexity = O ( 1 )

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i] != i + 1 and nums[nums[i] - 1] != nums[i]:
                tmp = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = tmp
        
        for i in range(len(nums)):
            if i + 1 != nums[i]:
                return nums[i]