我在 geeksforgeeks.com 上解決了這個問題，雖然我的解決方案設法通過了所有測驗用例，但我實際上使用了 .sort()，所以我知道它不符合 O(n) 的預期時間復雜度：我的意思是我們都知道沒有排序演算法適用于 O(n)，甚至沒有 Timsort 的最佳實作（這是 Python 使用的）。所以我去檢查網站的答案/解決方案，發現這個：
def printRepeating(arr, n):
# First check all the
# values that are
# present in an array
# then go to that
# values as indexes
# and increment by
# the size of array
for i in range(0, n):
index = arr[i] % n
arr[index] = n
# Now check which value
# exists more
# than once by dividing
# with the size
# of array
for i in range(0, n):
if (arr[i]/n) >= 2:
print(i, end=" ")
我試圖遵循該演算法背后的邏輯，但老實說不能，所以我測驗了不同的資料集，直到我發現它失敗了。例如：
arr = [5, 6, 3, 1, 3, 6, 6, 0, 0, 11, 11, 1, 1, 50, 50]
輸出：0 1 3 5 6 11 13 14
請注意：
- 數字 5 不在陣列中重復，
- 陣列中甚至沒有數字 13 和 14，并且
- 數字 50 既存在又重復，解決方案不會顯示它。
我已經向網站報告了這個問題，我只是想知道，既然這些問題應該被策劃，那么在 O(n) 中是否有解決方案。我最好的猜測是沒有，除非你能以某種方式在所有鍵/值的映射中插入 O(1) 中的每個重復數字。
uj5u.com熱心網友回復：
代碼不適用于您的示例資料集的原因是您違反了問題中給出的約束之一。輸入陣列（長度n）應該只包含從0到的值n-1。您的值 50 太大（因為您的串列中有 15 個元素）。該約束就是為什么添加n到現有值不會破壞事物的原因。您有一個小于 n 的原始值（可以用 提取arr[i] % n）和計數（可以用 提取arr[i] // n）。這兩個值相互堆疊，巧妙地重用現有陣列，無需額外空間。
uj5u.com熱心網友回復：
問題可以解決dict()。
對于這里的 Python：https ://docs.python.org/3.10/library/stdtypes.html#mapping-types-dict
它是一種以攤銷 O(1) 訪問的抽象資料型別，正如您所提到的，這正是您所需要的。
Python stdlib 也有collections.Counter，它是dict完成問題要求的 90% 的專業化。
編輯
哦，結果也必須排序。看起來他們希望您使用list()“作為dict”，通過它們自己的值作為索引將整數映射到它們的出現次數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/490915.html
上一篇：如何從網頁中獲取JSON？
下一篇：將串列中的序列化位連接成位元組