1

这是一个适用于(可能)任何高级编程语言的通用问题。情况如下:

假设我有一个字符串数组。比如说,我设法将一个短篇小说中的 500 000 个字符串放入一个数组中(假设您没有输入格式的选项)。因此,很可能会有任意数量的重复项。

我想获取这个字符串数组并创建另一个数组,其中包含该数组的唯一子集(?)(即:没有重复项)。在这种情况下,输入和输出都必须是数组,因此可能会限制您使用各种选项。

性能方面,最快的方法是什么?我目前正在使用线性搜索来检查一个单词是否已经存在,但由于它是一个线性搜索,我觉得可能有更快的方法,特别是如果我有不合理数量的字符串可以使用。像一本更大的小说!

4

2 回答 2

3

使用哈希集可能是最明智的做法——复杂度应该是 O(N)。

注意:大多数高级编程语言都包含一个从数组中删除重复项的函数的实现,例如PHP

于 2011-04-19T13:48:37.177 回答
1

如果您要在其中放入数以万计的单词,那么有向无环单词图是我所知道的最有效的数据结构。

然而,它在概念上是一个非常简单的数据结构。

于 2011-04-19T14:05:41.167 回答