287. 寻找重复数

Difficulty
Medium
Tags
双指针
URL
https://leetcode-cn.com/problems/find-the-duplicate-number/
Star
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
提示：
  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
通过次数214,461提交次数329,085
 

法 1 双指针

思路
快慢指针，一个时间复杂度为O(N)的算法。
  • 其一，对于链表问题，使用快慢指针可以判断是否有环。
  • 其二，本题可以使用数组配合下标，抽象成链表问题。但是难点是要定位环的入口位置。
举个例子：nums = [2,5, 9 ,6,9,3,8, 9 ,7,1]，构造成链表就是：2->[9]->1->5->3->6->8->7->[9]，也就是在[9]处循环。
  • 其三，快慢指针问题，会在环内的[9]->1->5->3->6->8->7->[9]任何一个节点追上，不一定是在[9]处相碰，事实上会在7处碰上。
  • 其四，必须另起一个while循环定位环入口位置[9]。这里需要数学证明。
举个栗子
以[1,3,4,2,2]为例，0(索引0)->1(索引0的数字nums[0]，并且作为下一个数字的索引)->3(nums[1])->2->(nums[3])->4(nums[2])->2(nums[4])， 即 0 →1→3→2→4→2→4
2→4→2为环，2为环的入口
利用快慢指针找到环的起始位置： （1）快慢指针都初始化为0（即索引0） （2）快指针fast 每次走2步，慢指针slow 每次走1步，直到两指针相遇 （3）然后fast再设置为0，slow位置不动，并且两指针每次都走一步，直到两指针相遇，相遇点即为环的起始点，也是我们要找的重复数字。
题解
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        fast, slow = 0, 0
        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]
            # 在环中相遇
            if fast == slow:
                fast = 0
                while nums[slow] != nums[fast]:
                    fast = nums[fast]
                    slow = nums[slow]
                
                return nums[slow]

法2 原地 hash

思路
参考
♠️
442. 数组中重复的数据 ，但是本题要求不能交换数据，所以不太适用
题解
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
				# 把数字放到正确的位置上
        for i in range(0, len(nums)):
            idx = nums[i]-1
            while nums[idx] != idx + 1:
                nums[i], nums[idx] = nums[idx], nums[i]
                idx = nums[i] - 1

        
        for i in range(0, len(nums)):
            if nums[i] != i+1:
                return nums[i]