如何高效地查找Java数组中的重复整数？

在 Java 数组中查找重复项

问题

您有一个整数数组，并且希望有效地识别任何重复项。您的初始代码尝试比较每对元素，但在不存在重复项时无法准确检测重复项。

问题

代码中的缺陷在于其依赖于初始化的重复项标志在所有情况下都为 false。如果没有找到重复项，则在检查对角线元素时（即，当 j == k 时），循环仍会将重复项设置为 true。

更细致的解决方案

要解决此问题，请确保仅当找到实际重复项时，重复项标志才会设置为 true。这可以通过在 j == k 时省略 zipcodeList[j] 与其自身的比较来实现。

这是修改后的代码：

duplicates = false;
for (int j = 0; j < zipcodeList.length; j++) {
    for (int k = 0; k < zipcodeList.length; k++) {
        if (k != j && zipcodeList[k] == zipcodeList[j]) {
            duplicates = true;
        }
    }
}

更快的方法

上述解决方案的运行时复杂度为 O(n²)，其中 n 是 大批。对于大型数组，这种方法可能效率低下。

检测重复项的更有效方法是利用基于哈希的方法，将时间复杂度降低到 O(n)。下面是一个使用 HashSet 的示例：

boolean duplicates(int[] zipcodeList) {
    Set<Integer> lump = new HashSet<>();
    for (int zipcode : zipcodeList) {
        if (lump.contains(zipcode)) {
            return true;
        }
        lump.add(zipcode);
    }
    return false;
}

或者，可以使用 boolean[] 数组（位图）来跟踪先前遇到的元素并在元素出现时将重复项设置为 true，从而实现 O(n) 解决方案。第二次遇到。

结论

根据输入数组的大小和重复的频率，应调整方法的选择以优化效率。

以上是如何高效地查找Java数组中的重复整数？的详细内容。更多信息请关注PHP中文网其他相关文章！