查找数组中具有最小索引的第一个重复元素

Question

我有一个包含一些重复元素的数组，如下所示：

找到第二次出现的索引最小的第一个重复数字。换句话说，如果重复的数字超过 1 个，则返回第二次出现的索引比第二次出现的另一个数字小的数字。如果没有这样的元素，返回-1

对于 a = [2, 1, 3, 5, 3, 2]，输出应该是 firstDuplicate(a) = 3。

有 2 个重复：数字 2 和 3。第二次出现 3 的索引比第二次出现的 2 小，所以答案是 3。

我试过这个：

int firstDuplicate(int[] a) {
  Set<Integer> set = new HashSet<>();
  Map<Integer, Integer> hm = new HashMap<Integer,Integer>();
  Map.Entry<Integer, Integer> min = null;
  for(int i=0;i<a.length;i++){
       // if(!hm.containsKey(a[i]))
              hm.put(a[i],i);
  }
  for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
        if(min == null || entry.getValue() < min.getValue()){
              min = entry;
        }
  }
  return min == null ? new Integer(-1) : min.getKey();

}

它不起作用，但我在网上找到了另一个解决方案，如下所示：

int firstDuplicate(int[] a) {
  Set<Integer> set = new HashSet<>();
  Map<Integer, Integer> hm = new HashMap<Integer,Integer>();
  Map.Entry<Integer, Integer> min = null;
  for(int i=0;i<a.length;i++){
        if(set.add(a[i])==false && !hm.containsKey(a[i]))
              hm.put(a[i],i);
  }
  for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
        if(min == null || entry.getValue() < min.getValue()){
              min = entry;
        }
  }
  return min == null ? new Integer(-1) : min.getKey();

}

任何人都可以在这里向我解释 Hashset 的使用，因为它不允许重复，所以 if 条件如何可行。

Answer 1

您第一次尝试失败的原因是您将数组元素作为键添加到 中，Map而没有检查它们是否已经存在，这意味着在完成填充Map.

您找到的替代代码做了一些不同的事情。它使用 theSet来确定当前数组元素是否已经出现在数组的较早位置，如果是这种情况，它只会将它作为键添加到 the Maponly 如果它不存在。这意味着Map将只包含在数组中多次出现的元素，并且与每个元素关联的索引是第一个重复项的出现。即对于数组{2, 1, 3, 5, 3, 2}，Map将包含{2=5, 3=4}. 然后它将返回具有最小值的键（对应于第一个重复项的索引）。

但是，这Map是不必要的，因为您只需要找到一个副本，而不是所有副本。使用Set来定位第一个重复项并返回它：

int firstDuplicate(int[] a) 
{
    Set<Integer> set = new HashSet<>();
    for(int i=0;i<a.length;i++){
        if(!set.add(a[i])) {
            return a[i];
        }
    }
    return -1; // no duplicates found 
}

如果已经包含您要添加的元素，则这依赖于set.add()返回。一旦它第一次返回，您就会找到第一个副本。falseSetfalse

Answer 2

我强烈建议您尝试此操作以获得正确的结果

你可以让它更有效的时间复杂度 O(n)

int firstDuplicate(int[] a){
int n = a.length;
for(int i=0; i<n; i++)
{
   if(a[Math.abs(a[i])-1]<0) return Math.abs(a[i]);
   else a[Math.abs(a[i])-1] = - a[Math.abs(a[i])-1];
}
return -1;
}