在数组中查找重复的算法

Question

我有一个分配来创建一个算法来查找包含数字值的数组中的重复项.但它没有说出哪种数字,整数或浮点数.我写了以下伪代码:

 FindingDuplicateAlgorithm(A) // A is the array
      mergeSort(A);
      for  int i <- 0 to i<A.length
           if A[i] == A[i+1]
                 i++
               return  A[i]
           else
                 i++

我创建了一个有效的算法？我认为我的算法存在问题,它会多次返回重复的数字.例如,如果数组包含2对2的两个索引,我将在输出中有... 2,2,... 如何更改它只返回每个重复一次？我认为它对于整数来说是一个很好的算法,但它对浮点数也有效吗？

Answer 1

要处理重复项,您可以执行以下操作:

if A[i] == A[i+1]:
    result.append(A[i]) # collect found duplicates in a list
    while A[i] == A[i+1]: # skip the entire range of duplicates 
        i++               # until a new value is found

Answer 2

你想在Java中找到Duplicates吗？

您可以使用HashSet.

HashSet h = new HashSet();
for(Object a:A){
   boolean b = h.add(a);
   boolean duplicate = !b;
   if(duplicate)
       // do something with a;
}

add()的返回值定义为:

如果集合尚未包含指定的元素,则返回true.

编辑: 我知道HashSet针对插入进行了优化并包含操作.但我不确定它的速度是否足够快.

EDIT2: 我见过你最近添加了家庭作业标签.我不喜欢我的回答,如果它是家庭作业,因为它可能是"高级"的算法课程

http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashSet.html#add%28java.lang.Object%29