Method 1:
快慢指针

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:

        #reference: https://keithschwarz.com/interesting/code/?dir=find-duplicate

        #TC: O(len(nums))
        #SC: O(1)

        fast = 0
        slow = 0

        while(True):
            slow = nums[slow]
            fast = nums[nums[fast]]

            if fast == slow:
                break

        find = 0

        while(True):
            find = nums[find]
            slow = nums[slow]

            if find == slow:
                break

        return slow

Method 2:
二分法

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:

        #TC: O(n log n)      n=len(nums)
        #SC: O(1)

        upper = max(nums)
        lower = min(nums)

        while(lower < upper):
            mid = lower + (upper - lower) / 2

            count_lower = 0
            count_upper = 0
            count_mid = 0

            for ele in nums:
                if lower <= ele < mid:
                    count_lower += 1
                elif upper >= ele > mid :
                    count_upper += 1
                elif ele == mid:
                    count_mid += 1
            if count_mid > 1:
                return int(mid)

            elif count_lower < count_upper:
                lower = int(mid) + 1
            elif count_lower > count_upper:
                upper = int(mid)

        return lower