如何在 O(n) 時間和 O(1) 空間內找到從 0 到 n-1 的數字數組中的重複項？

在O(n) 時間和O(1) 空間中找出重複項

給定一個包含n 個元素的數組，其中包含從0 到n 的數字-1，其中某些數字可能會出現多次，目標是在O(n) 時間內找到重複元素並使用恆定的記憶體空間。

為了實現這一點，我們可以利用一種有趣的方法，該方法不會不需要哈希表等額外的資料結構。

建議的演算法運算如下：

1. 排列循環：

   • 從0 到n-1 迭代的數組。
   • 在此循環內，執行以下步驟，直到 A[A[i]] 等於 A[i]。這意味著元素 A[i] 處於正確的位置。
   • 將 A[i] 與 A[A[i]] 交換。這有效地將元素 A[i] 向正確位置移動了一步。

2. 重複辨識循環：

   • 再次遍歷數組，從 i 從 0 到 n-1。
   • 如果 A[i] 不等於 i，則表示索引 A[i] 處有 i 的重複項。
   • 將 A[i] 列印為重複項。

此演算法可確保識別所有重複元素。外循環運轉n次，內循環最多運行n-1次。因此，此演算法的運行時間為 O(n)。它不使用任何額外的資料結構，這意味著它在 O(1) 空間中運作。

提供的程式碼範例了該演算法在 C 中的實作。

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