""" No. 287 寻找重复数 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 示例 1: 输入: [1,3,4,2,2] 输出: 2 示例 2: 输入: [3,1,3,4,2] 输出: 3 说明： 不能更改原数组（假设数组是只读的）。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n2) 。 数组中只有一个重复的数字，但它可能不止重复出现一次。 """


# 方法一、【排序】如果对数字进行排序，则任何重复的数字都将与排序后的数组相邻。
class Solution:
    def findDuplicate(self, nums):
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                return nums[i]

# 方法二、【哈希表】如果我们在数组上迭代时存储每个元素，我们可以在哈希表中查询每个元素。
class Solution:
    def findDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)

# 方法三、【双指针】类似于链表找环的题目，快慢指针如果能够相遇即有环，即重复数

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        walker=0
        runner=0
        while(1):                           # 与链表不同的是可以一直循环直到找到环形入口
            walker = nums[walker]           # 相当于 walker = walker.next
            runner = nums[nums[runner]]     # 相当于 runner = runner.next.next
            if(walker == runner):           # 相遇则退出循环
                break
        runner = 0                          # runner回到起点
        while(1):
            runner = nums[runner]           # 速度保持一致
            walker = nums[walker]
            if(runner == walker):           # 再次相遇的点即环形入口点
                return runner