найти первый повторяющийся элемент в массиве с минимальным индексом

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здесь, так как он не допускает дублирования, так как это, если условие будет работоспособным.

Answer 1

Я настоятельно рекомендую вам попробовать это, чтобы получить правильные результаты

вы можете сделать это более эффективным время сложности 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;
}

Answer 2

Вы можете использовать Java 8 с лямбда и потоком.

Вот код в одной строке:

Set<Integer> allItems = new HashSet<>();
Arrays.stream(a).filter(i -> !allItems.add(i)).findFirst().orElse(-1)

возвращает то, что вы ожидаете

Answer 3

Существует два способа решения этой проблемы: с помощью HashSet с временной сложностью o (n) и с помощью вложенных циклов o (n2)

for(int i = 0; i < a.length; i++){
    for(int j = i +1; j < a.length; j++){
           if(a[i] == a[j]){
                   System.out.println(a[i]);
                   return;
           }
     }
 }

Или вы можете сделать это более эффективной по времени.O (n)

int index -1;
Set<Integer> hashSet = new HashSet<Integer>();
for(int i = a.length-1; i >= 0; i--){
     if(hashSet.contains(a[i])){
           index = i;
     }else{
           hashSet.add(a[i]);
     }
}
 System.out.println(a[index]);

Answer 4

Причина, по которой ваша первая попытка не удалась, заключается в том, что вы добавляете элементы массива в качестве ключей к Map, не проверяя, существуют ли они уже, что означает, что вы не можете знать, есть ли какие-либо дубликаты к тому времени, как вы закончите заполнятьMap.

Альтернативный код, который вы нашли, делает что-то другое.Он использует Set, чтобы определить, появился ли текущий элемент массива ранее в массиве, и если это так, он добавляет его в качестве ключа к Map, только если его там еще нет.Это означает, что 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(), возвращающего false, если Set уже содержит элемент, который вы хотите добавить.Как только он возвращает false в первый раз, вы нашли первый дубликат.