205 - 287 寻找重复数

题目

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2] 输出: 2

示例 2:

输入: [3,1,3,4,2] 输出: 3

说明：

1. 不能更改原数组（假设数组是只读的）。

2. 只能使用额外的 O(1) 的空间。

3. 时间复杂度小于 O(n2) 。

4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

解答

只能想到用哈希表，遍历一下、存一下。但这就用了额外空间了。

两分法

https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-si-lu-ji-dai-ma-python-by-liweiwei1419/

通过值来做两分，比如数组是1-7，中间值是4，那么统计所有小于4的个数，如果多余3，就说明重复的数在1-3之间。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        l = 1
        r = len(nums)-1
        while l < r:
            mid = (l+r) >> 1
            count = 0
            for i in nums:
                if i <= mid:
                    count += 1
            if count > mid:
                r = mid
            else:
                l = mid+1
        return l

Runtime: 104 ms, faster than 6.37% of Python3 online submissions for Find the Duplicate Number.

Memory Usage: 15.1 MB, less than 17.86% of Python3 online submissions for Find the Duplicate Number.

快慢指针

https://leetcode-cn.com/problems/find-the-duplicate-number/solution/kuai-man-zhi-zhen-de-jie-shi-cong-damien_undoxie-d/

因为数组的内容就是数字，也就可以当成索引，去找下一个数字。

而且因为有重复的数字，所以不会越界，反而能形成环。

所以可以用快慢指针来完成

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        fast = 0
        slow = 0
        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]
            if fast == slow:
                break
        finder = 0
        while True:
            finder = nums[finder]
            slow = nums[slow]
            if slow == finder:
                break
        return slow

Runtime: 64 ms, faster than 81.66% of Python3 online submissions for Find the Duplicate Number.

Memory Usage: 15.2 MB, less than 17.86% of Python3 online submissions for Find the Duplicate Number.