Description

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, $O(1)$ extra space.
  3. Your runtime complexity should be less than $O(n^2)$.
  4. There is only one duplicate number in the array, but it could be repeated more than once.

Solutions

1. 暴力解法

　　首先，这个问题看起来很简单，不是就找重复的嘛？我直接用 List 或者用 Dict 来找就好了，但是细看规则，这里要求只能用 $O(1)$ 的 Space Complexity。但是我们可以先试下：

# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        dup_list = {}
        for item in nums:
            if item in dup_list:
                return item
            else:
                dup_list[item] = 1

　　用 dict 写完后想用 list 也试下，结果发现改成 list 实现会报错 Time Limit Exceeded。

# Time Complexity: O(n^2)
# Space Complexity: O(n)
 class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        dup_list = []
        for item in nums:
            if item in dup_list:
                return item
            else:
                dup_list.append(item)

　　分析了下原因很明显，因为用 list 的 in 来查找，其实就是 $O(n)$ 的时间复杂度啊！

2. 二分查找

　　我们先找到对应的 mid 值，然后遍历数组中所有的数，统计小于等于 mid 的数的个数，如果个数小于等于 mid，说明重复的数是在 [mid+1, n] 之间，反之在 [1, m-1]。

# Time: O(nlogn)
# Space: O(1)
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        l, r = 0, n - 1
        while l <= r:
            mid = l + ((r - l) >> 1)
            cnt = 0
            for num in nums:
                if num <= mid:
                    cnt += 1
            if cnt <= mid:
                l = mid + 1
            else:
                r = mid - 1
        return l

# 53/53 cases passed (76 ms)
# Your runtime beats 28.57 % of python3 submissions
# Your memory usage beats 17.86 % of python3 submissions (15.2 MB)

　　值得注意的是，除以 2 可以用位操作！

3. 链表有环找入口

　　接着想办法找到空间复杂度为 $O(1)$ 的方式，看提示说可以将这个问题看成链表中判断是否有环的情况，然后有环的话找对应的环的入口。

[1,3,4,2,2]
0->1->3->2->4->2 cycle: 2->4->2

[3,1,3,4,2]
0->3->4->2->3->4->2 cycle 3->4->2->3

# Time Complexity: O(n)
# Space Complexity: O(1)
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        fast, slow = nums[0], nums[0]
        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]
            if fast == slow:
                break
        fast = nums[0]
        while fast != slow:
            fast = nums[fast]
            slow = nums[slow]
        return fast
# Runtime: 68 ms, faster than 98.85% of Python3 online submissions for Find the Duplicate Number.
# Memory Usage: 16.2 MB, less than 7.14% of Python3 online submissions for Find the Duplicate Number.

　　这种想法的创作动机是什么呢？

4. 位操作

　　什么骚操作，都没看懂。

# Time Complexity: O(kn)
# Space Complexity: O(1)
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        res, n = 0, len(nums)
        MAX_BITS = 32
        for i in range(MAX_BITS):
            bit, cnt1, cnt2 = 1 << i, 0, 0
            for j in range(n):
                if j & bit > 0:
                    cnt1 += 1
                if nums[j] & bit > 0:
                    cnt2 += 1
            if cnt2 > cnt1:
                res += bit
        return res
# Runtime: 216 ms, faster than 5.73% of Python3 online submissions for Find the Duplicate Number.
# Memory Usage: 16.1 MB, less than 7.14% of Python3 online submissions for Find the Duplicate Number.

　　参考中说对于每一位，0到 n-1 中所有数字中该位上的1的个数应该是固定的，如果 nums 数组中所有数字中该位上1的个数多了，说明重复数字在该位上一定是1，这样我们把重复数字的所有为1的位都累加起来，就可以还原出了这个重复数字。🤔

References

  1. 287. Find the Duplicate Number
  2. 位操作解法