Posted on 2023-09-19 18:00
Uriel 閱讀(75)
評論(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