我有一个任务，需要创建一个算法在包含数字值的数组中查找重复项。但是任务没有说明这些数字属于哪种类型，整数还是浮点数。我已经编写了以下伪代码：
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,...。我该如何更改它，以仅返回每个重复项一次？ 我认为对于整数而言，这是一个好的算法，但对于浮点数呢？
为了处理重复项，您可以执行以下操作：
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
value1 == value2 时，两个浮点值才是相同的。 - Andreas Brincka == b，那么值a是另一个值b的重复，没有其他定义方式。 - Andreas Brinck你想在Java中查找重复项吗？
你可以使用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针对插入和包含操作进行了优化。但我不确定它是否足够快以满足您的要求。
编辑2： 我看到您最近添加了作业标签。如果这是一项作业，我不建议使用我的答案，因为它可能对算法课程来说过于“高级”。
http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashSet.html#add%28java.lang.Object%29
您的答案看起来相当不错。首先进行排序，然后简单地检查相邻值可以得到O(n log(n))的复杂度，这非常高效。
归并排序是O(n log(n))，而检查相邻值只是O(n)。
不过有一件事（正如其中一个评论中提到的），您的伪代码会导致堆栈溢出（哈哈）。内部循环应该是（在Java中）：
for (int i = 0; i < array.length - 1; i++) {
...
}
如果您想显示哪些数字（和/或索引）是重复的，那么您需要将它们存储在一个单独的列表中。
O(n)算法：遍历数组并尝试将每个元素输入具有数字作为哈希键的哈希表/集合中。如果无法输入，则为重复项。
你的算法存在缓冲区溢出。 i 从0开始，因此我假设数组 A 的索引是基于零的，即第一个元素是 A [0]，最后一个元素是 A [A.length-1] 。现在，i 计数到 A.length-1，并且在循环体中访问 A[i+1]，这对于最后一次迭代来说超出了数组范围。或者简单地说：如果您要将每个元素与下一个元素进行比较，则只能进行长度-1次比较。
如果您只想报告重复项一次，我会使用一个布尔变量 firstDuplicate，当您发现重复项时将其设置为false，并在数字与下一个数字不同的情况下将其设置为true。然后，仅在 firstDuplicate 为true时报告第一个重复项，即仅在报告重复数字时报告它们。
public void printDuplicates(int[] inputArray) {
if (inputArray == null) {
throw new IllegalArgumentException("Input array can not be null");
}
int length = inputArray.length;
if (length == 1) {
System.out.print(inputArray[0] + " ");
return;
}
for (int i = 0; i < length; i++) {
if (inputArray[Math.abs(inputArray[i])] >= 0) {
inputArray[Math.abs(inputArray[i])] = -inputArray[Math.abs(inputArray[i])];
} else {
System.out.print(Math.abs(inputArray[i]) + " ");
}
}
}