arrays - 数组算法中的匹配

Question

我有一系列项目，我需要找到匹配的项目（重复项）。我现在正在运行最简单的 O(n^2) 算法。项目类型并不重要，但如果你想知道它的图像。

myarray;   
for(i = 0; i < myarray.length - 1; i++) 
    for(int j = i+1; j < myarray.length; j++) 
        if(myarray[i] = myarray[j]) 
           output(names of items);

我尝试了维基百科和谷歌，但无法给出答案。任何语言的任何链接、算法或代码都会很棒。

Answer 1

如果您可以找到项目的订单，请对它们进行排序。然后找到相等的项目将非常简单，因为它们将彼此相邻。

这只是 O(n*Log(n))。

Answer 2

要查找数组中的重复项，您可以对列表进行排序和扫描，在O(n log n). 如果您只想输出重复项，并且内存不是问题，您可以保留您已经看到的元素的 hashSet，遍历数组，检查当前元素是否在您的集合中。如果是，则将其作为重复输出，否则将其插入到集合中。那将是O(n)

Answer 3

与其对相邻项目进行排序然后比较，不如将每个项目添加到自平衡二叉树中，这样您就可以免费获得“已经存在”检查（有点）。