https://leetcode-cn.com/problems/find-the-duplicate-number/

好久不写LeetCode的了,主要是最近有点携带刷题了,再加上好多题,也没什么营养。

为了找回一下状态,找一些典型题重新开始写。

# -*- coding:utf-8 -*-

"""
┏┛ ┻━━━━━┛ ┻┓
      
      
 ┳┛  ┗┳ 
      
      
      
┗━┓   ┏━━━┛
   神兽保佑
   代码无BUG
   ┗━━━━━━━━━┓
        ┣┓
     ┏┛
┗━┓ ┓ ┏━━━┳ ┓ ┏━┛
┃ ┫ ┫ ┃ ┫ ┫
┗━┻━┛ ┗━┻━┛
"""


class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
fast = 0
while res != fast or fast == 0:
res = nums[res]
fast = nums[nums[fast]]
print()
print(res)
i = 0
while res != i:
res = nums[res]
i = nums[i]
return res


if __name__ == '__main__':
nums = [1, 2, 3, 4, 2, 2]
nums = [2, 5, 9, 6, 9, 3, 8, 9, 7, 1]
print(Solution().findDuplicate(nums))

思路:

这道题首先就是一个快慢指针问题—— 快慢指针是一个可以用于很多问题的技巧。

快慢指针中的快慢指的是指针向前移动的步长,每次移动的步长较大即为快,步长较小即为慢,常用的快慢指针一般是在单链表中让快指针每次向前移动2,慢指针则每次向前移动1。快慢两个指针都从链表头开始遍历,于是快指针到达链表末尾的时候慢指针刚好到达中间位置,于是可以得到中间元素的值。快慢指针在链表相关问题中主要有两个应用:

  • 快速找出未知长度单链表的中间节点 设置两个指针 *fast、*slow 都指向单链表的头节点,其中*fast的移动速度是*slow的2倍,当*fast指向末尾节点的时候,slow正好就在中间了。
  • 判断单链表是否有环 利用快慢指针的原理,同样设置两个指针 *fast、*slow 都指向单链表的头节点,其中 *fast的移动速度是*slow的2倍。如果 *fast = NULL,说明该单链表 以 NULL结尾,不是循环链表;如果 *fast = *slow,则快指针追上慢指针,说明该链表是循环链表。

比如我们举个例子:

有 列表 【2,5,9,6,9,3,8,9,7,1】

我们可以根据索引,将列表转换为链表:

2->9->1->5->3->6->8->7->9

为了防止画乱,只画出几步:

这样,我们就可以得到一个类似的链表:

我们使用快慢指针后,快慢指针会在数字8处相遇。

到这里,我们就可以知道,慢指针从数字2到数字8,快指针从数字2绕一圈后到数字8,也就是快的比慢的多走了一圈。

那如果,我们将慢的放回起点,他们就会在圈的起始地相遇,就是数字9。

就类似于,我跑100米能落你20米,那如果你比我提前20米跑,那么我们就会同时到终点。

分类: 算法

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注