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

在O(n) 時間和O(1) 空間中找出重複項：深入解釋

提出的問題涉及識別重複項數組中包含0 到n-1 範圍內的數字的元素。挑戰在於如何在 O(n) 時間複雜度內並且僅使用恆定 (O(1)) 記憶體空間來有效地實現這一目標。

所提出的解決方案採用了一種巧妙的技術，不需要雜湊表或其他附加資料結構。相反，它利用數組本身中的值來識別和標記重複元素。

1. 排列數組：

   內部循環排列基於以下邏輯的陣列：

   while A[A[i]] != A[i]
       swap(A[i], A[A[i]])
   end while

   此排列步驟可確保如果數組中存在元素x，則其至少一個實例將位於A[x]。這對於後續步驟至關重要。

2. 辨識重複項：

   外循環檢查每個元素A[i]:

   for i := 0 to n - 1
       if A[i] != i then
           print A[i]
       end if
   end for

   如果A [i] != i，則表示i 沒有出現在陣列中正確的位置。因此，它是一個重複元素，並且被印製。

3. 時間複雜度分析：

   此技術運行時間為 O(n) 時間。巢狀循環有一個迭代 n 次的外循環和一個最多執行 n - 1 次迭代的內循環（因為每次交換都會使一個元素更接近其正確位置）。因此，迭代總數以n*(n - 1) 為界，即O(n^2)，但可以簡化為O(n)，因為n*(n - 1) = n^2 - n = n(n - 1) = n*n - n

4. 空間複雜度分析：

   演算法僅使用恆定空間，與輸入的大小無關。關鍵的見解是用於排列的空間已經存在於輸入數組中。不需要額外的儲存結構。

5. 附加說明：

   • 演算法假設陣列包含從0 到n 的整數- 1.
   • 即使🎜>即使存在重複項，時間複雜度也保持不變。
   • 此演算法對於小型到中等大小的陣列非常有效。對於大型數組，使用哈希表等資料結構的替代方法可能更合適。

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