找出一個(gè)數(shù)組中重復(fù)的數(shù)字(數(shù)組中的數(shù)字來自1-n,只有一個(gè)數(shù)字重復(fù)出現(xiàn),可能出現(xiàn)兩次以上任何次數(shù))
看Discussion get了巧妙思路,把nums[a]=b聯(lián)想為a.next=b,這樣找出重復(fù)出現(xiàn)的數(shù)字就相當(dāng)于尋找一個(gè)鏈表中的環(huán)
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