Posted on 2023-09-19 18:00
Uriel 阅读(28)
评论(0) 编辑 收藏 引用 所属分类:
数据结构 、
闲来无事重切Leet Code
找出一个数组中重复的数字（数组中的数字来自1-n，只有一个数字重复出现，可能出现两次以上任何次数）
看Discussion get了巧妙思路，把nums[a]=b联想为a.next=b，这样找出重复出现的数字就相当于寻找一个链表中的环
1 #287
2 #Runtime: 473 ms (Beats 70.43%)
3 #Memory: 25 MB (Beats 91.14%)
4
5 class Solution(object):
6 def findDuplicate(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 slow, fast, ans = 0, 0, 0
12 while True:
13 slow = nums[slow]
14 fast = nums[nums[fast]]
15 if slow == fast:
16 while ans != slow:
17 ans = nums[ans]
18 slow = nums[slow]
19 return ans