găsește primul element duplicat dintr-un array cu indice minim (Programare, Java, Array-Uri, Hashset)

ra_pri a intrebat.

Am o matrice care conține câteva elemente duplicate, astfel :

găsiți primul număr duplicat pentru care a doua apariție are indicele minim. Cu alte cuvinte, dacă există mai mult de 1 numere duplicate, returnează numărul pentru care a doua apariție are un indice mai mic decât are a doua apariție a celuilalt număr. În cazul în care nu există astfel de elemente, se returnează -1

Pentru a = [2, 1, 3, 3, 5, 3, 2], rezultatul ar trebui să fie firstDuplicate(a) = 3.

Există două duplicate: numerele 2 și 3. A doua apariție a lui 3 are un indice mai mic decât a doua apariție a lui 2, deci răspunsul este 3.

Am încercat acest lucru :

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();

}

Nu merge, dar am găsit o altă soluție pe internet care este cam așa :

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();

}

Poate cineva să-mi explice, vă rog, cum se utilizează Hashset în acest caz, deoarece nu permite duplicate, deci cum va funcționa această condiție if.

Comentarii

  • Practic, se calculează un hashmap a cărui cheie este elementul, iar valoarea este indexul duplicatului său. Apoi, se efectuează o căutare a indicelui minim din hashmap. –  > Por Jean-Baptiste Yunès.
  • Set.add va returna false dacă setul conține deja obiectul pe care doriți să îl adăugați. Deci, verificând dacă valoarea de returnare este false puteți verifica dacă obiectul se afla deja în set. În cazul în care nu a fost încă în set (și este a doua apariție, nu una ulterioară), se salvează poziția acestuia într-o hartă. Rezultă o hartă cu toate duplicatele și prima lor apariție. În continuare, trebuie doar să vedeți care a fost prima dublă și ați terminat. Sincer să fiu, ați putea scurta foarte mult acest cod cu o logică de flux sau doar prin întoarcerea la primul fals, deoarece acesta este în mod evident cel mai vechi duplicat… –  > Por Ben.
5 răspunsuri
Eran

Motivul pentru care prima ta încercare a eșuat este faptul că adaugi elementele tabloului ca chei la Map fără a verifica dacă acestea sunt deja acolo, ceea ce înseamnă că nu puteți ști dacă există duplicate până când terminați de populat array-ul Map.

Codul alternativ pe care l-ai găsit face ceva diferit. Acesta utilizează Set pentru a determina dacă elementul curent al tabloului a apărut deja mai devreme în tablou, iar dacă este cazul, îl adaugă ca cheie la Map numai dacă nu se află deja acolo. Acest lucru înseamnă că Map va conține numai elemente care apar de mai multe ori în array, iar indicele asociat fiecărui element este apariția primului duplicat. De exemplu, pentru matricea {2, 1, 3, 5, 3, 2}, , indicele Map va conține {2=5, 3=4}. Apoi va returna cheia cu cea mai mică valoare (care corespunde cu indicele primului duplicat).

Cu toate acestea, se va utiliza Map nu este necesar, deoarece trebuie să găsiți doar un singur duplicat, nu toate. Utilizați opțiunea Set pentru a localiza primul duplicat și a-l returna:

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 
}

Acest lucru se bazează pe set.add() returnarea false în cazul în care Set conține deja elementul pe care doriți să îl adăugați. Odată ce se returnează false pentru prima dată, înseamnă că ați găsit primul duplicat.

Comentarii

  • Acest cod nu returnează primul duplicat care are un indice minim. Acesta returnează primul duplicat. Pentru exemplul din întrebare, acesta returnează 2 și nu 3 –  > Por Davide Lorenzo MARINO.
  • @DavideLorenzoMARINO Nu, va returna 3, deoarece al doilea 3 din matrice va fi întâlnit înainte de al doilea 2. –  > Por Eran.
Ms_Sri

V-aș recomanda cu tărie să încercați acest lucru pentru a obține rezultatele corecte

îl puteți face mai eficient complexitatea timpului 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;
}

Comentarii

  • Frumos, are o complexitate de timp O(n) și de spațiu O(1), deci mai eficient decât răspunsul acceptat. –  > Por meshkati.
  • Aceasta nu este o soluție generală. Este valabilă doar dacă toate elementele din a sunt mai mari decât 1 și sunt cel mult a.length. –  > Por oscfri.
  • Ar putea cineva să explice, vă rog, ideea din spatele acestei soluții? –  > Por newbieee.
Arnauld Alex

Puteți folosi java 8 cu lambda și stream.

Iată codul într-o singură linie :

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

returnează ceea ce vă așteptați

MichaelB

Există două moduri de a implementa această problemă, prin utilizarea unui HashSet cu complexitate de timp o(n) și prin utilizarea buclelor imbricate 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;
           }
     }
 }

Sau puteți să o faceți mai eficient complexitatea în timp 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]);

Adedamola
int firstDuplicate(int[] a)
    {
        int DupIndex = 0;
        int DupValue = 0;
        for (int i = 0; i < a.Length; i++)
        {
            for (int j = i + 1; j < a.Length; j++)
            {
                if (a[i] == a[j])
               {
                    if (j < DupIndex)
                    {
                        DupIndex = j;
                        DupValue = a[i];
                    }
                    else if (DupIndex == 0)
                    {
                        DupIndex = j;
                        DupValue = a[i];
                    }
                }
            };
        };
        return (DupValue == 0) ? -1 : DupValue;
    }