如何有效检测 Java 数组中的重复整数？

识别 Java 数组中的重复项：一段旅程

在 Java 领域，经常遇到的一个完整任务是在整数数组 (int []）。然而，当尝试识别这些重复项时，会出现一个常见的陷阱。让我们探讨这个问题及其解决方案。

考虑以下代码：

int[] zipcodelist = // ...

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

此代码旨在确定给定的邮政编码列表是否包含任何重复元素。但是，它无法考虑不存在重复项的情况。因此，重复的结果总是为真。

识别缺陷

为了理解这个缺陷，让我们分析一下逻辑。该代码具有嵌套循环，用于将列表中的每个元素与其他每个元素进行比较。如果任何两个元素匹配，则重复项设置为 true，表明存在重复项。但是，当没有重复项时，循环不可避免地会将元素与其自身进行比较。对于每个元素，此自我比较会将重复项设置为 true。

正确的方法

为了确保正确检测重复项，代码应排除自我比较。实现此目的的一种方法是修改嵌套循环结构，如下所示：

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

此修改通过在下一个索引 (k=j 1) 处启动内部循环来跳过自比较。

探索替代解决方案

虽然正确的方法有效，但还有更快的替代方案。考虑以下基于哈希图的解决方案：

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

此解决方案利用哈希集来有效地检查重复元素。每个元素都会添加到哈希集中，如果元素已存在，则表示重复。

另一种有效的方法涉及使用位图：

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];
   java.util.Arrays.fill(bitmap, false);
   for (int item : zipcodelist)
     if (!(bitmap[item] ^= true)) return true;
   }
   return false;
}

此解决方案创建一个位图数组的大小等于数组中的最大可能值 (MAXZIP)。然后，它使用位操作为输入数组中遇到的每个元素设置相应的位。如果已设置任何位，则表示重复。

基准测试结果

为了评估这些方法的性能，我们使用不同的列表大小进行了基准测试。结果表明，位图方法在效率方面明显获胜，特别是对于较大的列表：

Array Size	Bitmap (ms)	Hash Set (ms)	Nested Loops (ms)
10	0.0	0.0	0.0
1,000	0.0	0.0	0.0
10,000	0.0	0.0	100.0
100,000	0.0	0.16	9,923.3

结论

一旦理解了陷阱，识别 Java 数组中的重复项就可以是一项简单的任务。通过避免自我比较或利用哈希集和位图等替代方法，可以实现高效且准确的重复检测，从而优化 Java 应用程序的性能。

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