java - 在具有最小索引的数组中找到第一个重复元素

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 的时间。

您找到的替代代码做了一些不同的事情。它使用 Set 来确定当前数组元素是否已经出现在数组的前面，如果是这样，它就将它作为键添加到 Map 中(如果不是)已经在那了。这意味着 Map 将只包含在数组中出现多次的元素，并且与每个元素关联的索引是第一个重复出现的元素。 IE。对于数组 {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() 在 Set 已经包含您要添加的元素时返回 false。一旦它第一次返回 false，您就找到了第一个重复项。