如何有效地从字符串中删除重复的字符？

是否有可能删除字符串中的重复字符而不保存数组中已经看到的每个字符并检查新字符是否已经存在于该数组中？这似乎效率很低。当然必须有更快的方法？如何有效地从字符串中删除重复的字符？

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

如何有效地从字符串中删除重复的字符？

回答

相关问题