資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學用 Python 查詢重複數字
假設我們有一個包含 n + 1 個整數的陣列 nums。成員範圍從 1 到 n。證明至少有一個重複數。假設只有一個重複數，我們必須找到重複的元素。因此，如果陣列形如 [1,3,4,2,2]，則重複元素為 2。
要解決這個問題，我們將按照以下步驟操作：
- a := nums[0] 且 b := nums[0]
- while True
- a := nums[nums[a]]
- b := nums[b]
- if a = b, 則退出迴圈
- ptr := nums[0]
- while ptr 不同於 b
- ptr := nums[ptr]
- b := nums[b]
- 返回 ptr
我們看看以下實現來加深理解：
示例
class Solution(object): def findDuplicate(self, nums): hare = nums[0] tortoise = nums[0] while True: hare = nums[nums[hare]] tortoise = nums[tortoise] if hare == tortoise: break ptr = nums[0] while ptr!=tortoise: ptr = nums[ptr] tortoise = nums[tortoise] return ptr ob1 = Solution() print(ob1.findDuplicate([3,1,3,4,2]))
輸入
[3,1,3,4,2]
輸出
3
更新日期： 04-May-2020
2K+ 次瀏覽
廣告