利用 Python 從元素列表中查詢重複項的程式

假設我們有一個名為 nums 的元素列表，大小為 n + 1，它們選自範圍 1、2、...、n。眾所周知，根據鴿巢原理，一定會有重複元素。我們必須找到重複元素。我們的目標是在 O(n) 時間和常數空間內完成此任務。

因此，如果輸入類似 nums = [2,1,4,3,5,4]，那麼輸出將是 4

為了解決這個問題，我們將按照以下步驟進行操作 −

  • q := nums 中所有元素的和

  • n := nums 的大小

  • v := ((n - 1)*(n)/2) 的下限

  • return q - v

示例

讓我們看看以下實現來更好地理解

def solve(nums):
   q = sum(nums)
   n = len(nums)
   v = (n - 1) * (n) // 2
   return q - v

nums = [2,1,4,3,5,4]
print(solve(nums))

輸入

[2,1,4,3,5,4]

輸出

4

更新於： 2021-10-11

153 人檢視

開啟您的職業生涯

透過完成課程獲得認證

開始學習
廣告