如何在 O(n) 時間和 O(1) 空間的陣列中找到重複項？

在O(n) 時間和O(1) 空間中找出重複項的高效演算法

在本次程式設計挑戰中，我們尋求一種高效的演算法識別和列印整數數組中重複元素的演算法，範圍從0 到n-1，並可能重複。此挑戰需要一種在 O(n) 時間複雜度內運行且僅消耗恆定記憶體空間的演算法。

解決此問題的一種有效方法是「陣列修改」技術。演算法的工作原理如下：

1. 第一個循環：

   • 初始化一個迭代數組中每個元素的循環，表示為A[i].
   • 對每個A[i]，判斷A[A[i]]是否等於A[i]。
   • 如果不等於，則將A[i]與A[交換A[i]].

2. 第二個循環：

   • 重置循環以迭代每個A[i]再次。
   • 對於任何不等於 i 的 A[i]，印出 A[i]。此步驟識別重複元素，因為任何非重複元素的 A[A[i]] 都等於 i（即，它位於正確的位置）。

該演算法的運行時間為 O(n)，因為每個元素在第一個循環中最多檢查和修改一次。此外，由於沒有使用額外的資料結構，因此它僅利用 O(1) 空間。

例如，考慮輸入陣列 {1, 2, 3, 1, 3, 0, 6}。執行演算法後，陣列將被修改如下：

[1, 2, 3, 1, 3, 0, 0]

第二個循環然後列印重複元素 1 和 3。

以上是如何在 O(n) 時間和 O(1) 空間的陣列中找到重複項？的詳細內容。更多資訊請關注PHP中文網其他相關文章！