287. Find the Duplicate Number

Solution 1: Brute-Force (TLE)

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

Time Complexity: O(N^2)
Space Complexity: O(1)

Solution 2: Binary Search

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        lftIntval = 1
        rhtIntval = len(nums) - 1
        while(lftIntval < rhtIntval):
            mid = lftIntval + (rhtIntval - lftIntval) // 2
            valLessThanMidcnt = 0
            for val in nums:
                if val <= mid:
                    valLessThanMidcnt += 1
            
            # The repeated num is in the [mid+1, rhtIntval]
            if valLessThanMidcnt <= mid:
                lftIntval = mid + 1
            # The repeated num is in the [lftIntval, mid]
            else:
                rhtIntval = mid
        return lftIntval

Time Complexity: O(N*Log(N))
Space Complexity: O(1)

Solution 3: Fast Slow Pointers

Time Complexity: O(N)
Space Complexity: O(1)

Solution 4: Bitwise Operation

    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        highestBit = 31
        while ((n - 1) >> highestBit) == 0:
            highestBit -= 1

        duplicateNum = 0x0
        for bitI in range(highestBit+1):
            currentBitMask = 0
            nonDuplicBitMask = 0
            for idx in range(n):
                if nums[idx] & (1 << bitI):
                    currentBitMask += 1
                # The value of non-duplicate nums is [1, n-1]
                if idx & (1 << bitI):
                    nonDuplicBitMask += 1
                    
            if currentBitMask > nonDuplicBitMask:
                duplicateNum |= (1 << bitI)
                
        return duplicateNum

Time Complexity: O(N*Log(N))
Space Complexity: O(1)

Reference

https://www.cnblogs.com/grandyang/p/4843654.html
https://leetcode.com/problems/find-the-duplicate-number/discuss/1892921/Java-9-Approaches-Count-%2B-Hash-%2B-Sort-%2B-Binary-Search-%2B-Bit-%2B-Fast-Slow-Pointers

Follow-up: Missing Number

Follow-up2: Single Number

Follow-up3: Linked List Cycle II