如何有效检测 Java 数组中的重复整数？-java教程-PHP中文网

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

Barbara Streisand

发布： 2024-12-07 09:39:15

原创

192 人浏览过

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

识别 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)。然后，它使用位操作为输入数组中遇到的每个元素设置相应的位。如果已设置任何位，则表示重复。