在整数数组中查找重复项（带边界）

Question

以下是我写的问题描述和算法。有什么可以改进这个算法的地方吗？

给定一个大小未知的整数数组，其中只包含介于0和30之间的数字，请编写一个函数，返回一个整数数组，其中包含所有重复项。

int[] findDupes(int[] array) {
    int[] found = new int[30];
    int[] dupes = new int[30];
    int dupesCount = 0;
    for (int i = 0; i < array.length; i++) {
        if (found[array[i]] <= 1) {
            found[array[i]]++;              
        }else{
            continue;
        }
        if(found[array[i]] > 1){
            dupes[dupesCount++] = array[i];
            if (dupesCount == 30)
                break;
        }
    }
    if (dupesCount == 0)
        return new int[0];
    return dupes;
}

我假设运行该算法的最佳情况为n或30（以较小值为准），而最坏情况为n，因为我必须扫描整个数组以查找重复项。有任何意见吗？

- Srini Kandula

Answer 1

你想得很对，但是请问一下，这个代码块到底是干什么的？

    if(found[array[i]] > 1){
        dupes[dupesCount++] = array[i];
        if (dupesCount == 30)
            break;
    }

它何时触发？

使用一些样本，包括一个包含1000个0的数组，来逐步执行你的代码。

你具体返回了什么？为什么需要特殊处理0？

此外，最佳情况下的运行时间将大于30。使其在到达末尾之前停止的最小输入是什么？

- deinst

Answer 2

需要更精确地定义问题。整数只有1或2次出现吗？可能会出现0或3次吗？

如果整数只出现1或2次，并且整数范围在1到30之间；我会使用BitSet，并在找到整数时翻转位。当我完成读取原始数组时，所有为0的位将表示包含重复项的整数。

- illcar

---

@illcar：可能会有任意数量的出现。如果有多个出现，那么它们都是重复的。根据我对原帖问题的理解，我不需要检查重复出现的次数。 - Srini Kandula

Answer 3

这是嵌入了注释的修改版本。

int[] found = new int[3];
    int[] dupes = new int[3];
    int dupesCount = 0;
    for (int i = 0; i < array.length; i++) {
        if (found[array[i]] <= 1) {
            found[array[i]]++;              
        }
        if(found[array[i]] > 1){ //duplicate found
            dupes[dupesCount++] = array[i];

            // if 30 duplicate are found don't scan the array any more
            // since the distinct numbers are only 30
            if (dupesCount == 30) 
                break;
        }
    }
    if (dupesCount == 0)
        return null;
    return dupes;

- Srini Kandula

Answer 4

有点奇怪：

    if (found[array[i]] <= 1)              
    }else{
        continue;//happens if found[array[i]] > 1
    }
    if(found[array[i]] > 1){//usually don't get here, because of continue

continue语句是用来保证数字只被添加一次的吗？虽然它能够工作，但代码有误导性。

如果只有一个重复值，你需返回长度为30的数组吗？

我建议通过分解任务来让你的代码更加缓慢和优秀。

- Ishtar