287. 寻找重复数

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 经典的快慢指针 检查环。nums中的值，就是下一个链表节点的索引位置。
        # 由于是假定 值为下一个索引的位置，不是标准意义上带表头head的链表，假定位置时统一平移了。
        slow = nums[0]    # 起始没有 head，nums[0]已移动了一位。 
        # 由于起始索引总是0 而值在1～n，所以不用担心陷入单点死循环的问题。
        fast = nums[slow] # 起始没head， nums[slow]已移动了两位。
        while slow != fast:
            if fast > len(nums)-1 or slow > len(nums)-1:
                return "没重复数字"
            slow = nums[slow]
            fast = nums[nums[fast]]
        print("有重复数字，在%d位置"%fast)
        head1 = nums[0]   # 由于没有起始head指针，找交点时起点都移动一位，效果一样。
        head2 = nums[fast] 
        while head1 != head2:
            head1 = nums[head1]
            head2 = nums[head2]
        return head1