如何以最佳時間和空間複雜度找到數組中的重複項？

以最佳時間和空間複雜度找出重複項

簡介：
偵測重複元素的任務數組是程式設計中的一個普遍問題。雖然使用雜湊表等輔助資料結構的解決方案提供了簡單性，但它們會損害空間效率。本文提出了一個巧妙的演算法，可以在線性時間內辨識重複項，O(n)，同時保持恆定的空間消耗，O(1)。

問題陳述：
給定一個陣列從 0 到 n-1 的 n 個元素，其中某些數字可能出現多次，找出陣列中重複的元素。

最優演算法：

// Iterate through the array
for i = 0 to n - 1:
    // Swap elements until A[A[i]] = A[i]
    while A[A[i]] != A[i]:
        swap(A[i], A[A[i]])
    end while

// Identify duplicates based on A[i] != i
for i = 0 to n - 1:
    if A[i] != i:
        print A[i]
    end if
end for

見解：
演算法利用了這樣一個事實：數組中的每個元素理想情況下應位於其索引處。它使用陣列的元素來建立排列，確保存在的元素將映射到其正確的索引。第一個循環迭代數組，並確保每個元素透過交換達到其預期索引。

解釋：
第一個循環對數組進行排列，以便對於任何元素 x，如果它至少出現一次，一個實例將位於索引 A[x] 處。在每次交換中，都會修正與錯誤元素相對應的條目，從而保證交換總數受元素數量 N-1 的限制。

第二個循環透過列印每個元素的索引來識別重複項與索引不符的元素，表明它在原始數組中不存在。

結論：
演算法透過巧妙地利用輸入數組，有效地識別數組中的重複元素本身。其 O(n) 時間複雜度和 O(1) 空間複雜度使其適合廣泛的實際應用。

以上是如何以最佳時間和空間複雜度找到數組中的重複項？的詳細內容。更多資訊請關注PHP中文網其他相關文章！