首页 >Java >java教程 >如何高效地查找Java数组中的重复整数?

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

Susan Sarandon
Susan Sarandon原创
2024-12-11 01:36:13439浏览

How Can I Efficiently Find Duplicate Integers in a Java Array?

在 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(n2),其中 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中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn