寻找重复数

Leetcode Link: 287. 寻找重复数 - 力扣（LeetCode）

题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

解法一

思路：不考虑时间空间复杂度

排序后遍历一遍。

题解：时间 $O(NlonN+N)$，空间 $O(N)$

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        new_nums = nums.copy()
        new_nums.sort()
        last_val = new_nums[0]
        for val in new_nums[1:]:
            if val == last_val:
                return val
            last_val = val

我怎么首先想的是这个垃圾方法...!!! 最次也要一下子想到方法2啊！

解法二

思路： 遍历一遍，用集合 set 来做

题解：时间 $O(N)$，空间 $O(N)$

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        bucket = set()
        for val in nums:
            if val not in bucket:
                bucket.add(val)
            else:
                return val

解法三

思路：本题的特点，数字的范围是 [1,n]，同时只有 n+1 的长度。

根据这个特点对数组每个索引 (假设为 index=i) 构建一个链表节点 (val=不在乎, next = nums[i]) 即，这个链表中的一个节点，其值为当前位置的索引 (index)，其指向下一个链表的指针为该位置的值 (next_idx = nums[i])，进而下一个节点的值为 nums[i], 指针为 nums[nums[i]]

如果有重复的数字，那么就会指向同一个节点（假设 nums[i]==nums[j]，这两个节点会同时指向同一个节点，形成环）

那么本题就变成了，求一个有环链表的入口节点，参考问题环形链表

题解：

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 省略 fast = slow = 0 的初始化
        # 下面直接走了。
        fast = nums[nums[0]] 
        slow = nums[0]
        while(slow != fast):
            slow = nums[slow]
            fast = nums[nums[fast]]
        
        fast = 0
        while(slow != fast):
            slow = nums[slow]
            fast = nums[fast]
        
        return slow

本题的注意点

1. 实际上，本题相当于最开始初始化 fast = slow = 0，即两个指针都初始化为 0 节点。和环形链表对比，就是 dummy。而在实际写的时候，我们直接按照上图写，等价于初始化后先让 fast 走两步，再让 slow 走一步。
2. 在fast和slow第一次相遇后，必需将fast重置为初始节点0，而不是其他的节点，否则结果会报错。

解法四

二分法，review的时候在看。 使用「二分查法」搜索一个有范围的整数（结合「抽屉原理」） - 寻找重复数 - 力扣（LeetCode）

启发和联系

如果环形链表只是判断有没有环，slow和fast可以随便设置，只要保证slow走1fast走2即可。

如果需要寻找环形链表的入口，则初始化必需满足下列条件的一个

• 1
  • 第一次初始化 slow == fast, 相遇用while(1)+break来
  • 第二次初始化 fast = 第一次初始化的值
• 2
  • 第一次初始化 slow = node, fast = node.next，相遇直接用while(fast!=slow)来控制
  • 第二次初始化 fast = slow.pre 即第一次初始化时slow的上一个节点（在环形链表中是dummy）