如何有效地從字符串中刪除重複的字符？

是否有可能刪除字符串中的重複字符而不保存數組中已經看到的每個字符並檢查新字符是否已經存在於該數組中？這似乎效率很低。當然必須有更快的方法？如何有效地從字符串中刪除重複的字符？

2010-01-11 Chris

http://stackoverflow.com/questions/636977/best-way-to-remove-duplicate-characters-words-in-a-string此外，我相信有一個關於這個問題的代碼高爾夫球問題 – dmckee 2010-01-11 00:24:04

這裏是代碼高爾夫球問題多種解決方案，大概*糟糕*編碼風格http://stackoverflow.com/questions/1344352/code-golf-duplicate-character-removal-in-string – dmckee 2010-01-11 00:25:33

@dmckee是python特定的。也不完全一樣 – Chris 2010-01-11 00:26:04

您可以使用字符索引的布爾數組：

bool seen[256];

對於針對字節大小爲ASCII的字符，上述將是適當的。對於16位Unicode：

bool seen[65536];

等等。然後，對於字符串中的每個字符，這是一個簡單的查找，看看是否已經設置了該布爾值。

來源

2010-01-11 00:18:42

啊，是的，好主意......然後你可以在O（n）中把它拉下來。雖然重組字符串可能比其他任何事情都需要更多的時間。 – 2010-01-11 00:28:34

你也可以在O（n）中做到這一點，將你想保留的每個字符複製到一個新的字符串中。 – 2010-01-11 00:31:01

smaaaart。這是一個好主意。 – Chris 2010-01-11 00:40:22

使用LINQ

string someString = "Something I wrote quickly"; 
char[] distinctChars = someString.ToCharArray().Distinct(); 
string newString = new string(distinctChars);

來源

2010-01-11 00:14:39

string anotherString =「Mississippi」; ：D – mingos 2010-01-11 00:18:24

您可以使用正則表達式來一次匹配重複的字符。

來源

2010-01-11 00:14:57

我不知道是否有一個更簡單的算法。另一種方法是檢查第一個字符，然後檢查字符串的其餘部分並刪除所有相同的字符。然後爲第二個字符，第三個字符等執行此操作。這可能會節省內存，但會是O（n^2）。

您建議的算法是O（n * m），因爲它循環遍歷字符串中每個字符的數組。由於數組中的字符少於字符串中的字符，因此它最有可能比上述替代方法更快。該陣列會增加一些額外的內存需求，但不多。

然而，在大多數實際應用中，我懷疑您所建議的方法的效率會對性能產生任何顯着影響。可能還有其他方法（如正則表達式或LINQ區別），可能會有更多的性能開銷，但由於代碼簡化可能會值得。

來源

2010-01-11 00:17:44

使用數組也是O（n^2）。 – sepp2k 2010-01-11 00:19:50

Nitpickers'corner：原始海報的數組查找技術實際上是O（n * m），其中n是字符串的長度，m是您可能擁有的唯一字符數的界限。 – 2010-01-11 00:28:03

啊，你是對的，米會少於n。 – 2010-01-11 00:29:47

這將取決於你的數據的特點是什麼。字符串是否超長？預計會有很多重複嗎？字符串中的可能字符的範圍是什麼（英語？中文？）你有多少內存？產生的字符串是否仍需要訂購？

保留一套您在瀏覽時已經看到的字符是合理的。因此，如果您可以像那樣對字符串進行變異，那麼可能會對字符串進行排序，然後在您移動字符串時移除dupe。

如果字符串真的很長，您會希望保持運行時間接近O（n），這意味着保持一個位集（通常）或在極少情況下散列（如果可能的字符列表很大：中文？）或類似的東西，並跟蹤你所看到的角色，這樣你就可以在你走路的時候逐出它們。這裏也有很多實現細節，每次刪除一個字符時是否必須將內存中的所有字符都移回去，或者是否可以用空白或其他原位替換它。

如此反覆，取決於你是你要完成什麼，什麼樣的環境

來源

2010-01-11 00:18:40

的Python：

>>> ''.join(set("Something I wrote quickly")) 
' cegihkmlonqISrutwy'

顯然，這並不維持秩序。

來源

2010-01-11 00:27:25 Seth

如何有效地從字符串中刪除重複的字符？

回答

相關問題