任何更好的從線性數組中刪除重複元素的方法？

-1

我想從我的線性數組中刪除重複的元素。但我不想在O（n^2）時間複雜度中做它（因爲我使用了兩個for循環，這兩個循環在最壞情況下運行n次案例）有沒有什麼辦法在更短的時間內做到這一點？其他任何方法都會有很大的幫助。謝謝！任何更好的從線性數組中刪除重複元素的方法？

2013-10-09 The Game

1）如果你有一個線性數組，你應該能夠遍歷O（n）中的整個集合（單個循環）。 2）除非您選擇不同的數據結構（例如，對數組進行排序或使用散列圖），否則別無選擇，只能迭代列表至少一次。 – paulsm4

[在O（n）時間中在C/C++中從數組中刪除重複項]（http://stackoverflow.com/questions/7693540/removing-duplicates-from-an-array-in-cc-in- on-time） –

@ paulsm4-我必須刪除數組中的所有重複對象。因此，對於數組中的每個元素，我必須遍歷整個數組，然後它將花費O（n^2）。 –

您可以在O（n log n）中排序，然後通過檢查相鄰元素是否相同來刪除一個額外循環中的重複項。時間：O（n日誌n）

2013-10-09 21:12:25

除此之外，如果您在排序階段跟蹤原始位置（不會改變它的O（n log n）-ness），則可以將剩餘的元素按照O（n） ... – twalberg

回答