Trouver un élément en double dans un tableau?

J’ai vu une question d’entrevue comme suit:

Un numéro du tableau est en cours de duplication.

La solution simple est la suivante:

for(int i=0;i<n;i++){ { dup = false; for(j=0;j<n;j++){ if(i!=j && a[i]= a[j]){ dup = true; } if(dup == true) return a[i] } } 

Mais je veux l’implémenter dans O (n log (n)) et dans le temps O (n). Comment puis-je le faire?

Triez le tableau (cela peut être fait dans le premier O (n Log n), puis la comparaison doit être faite pour les éléments adjacents. Ou mettez simplement le tableau dans une table de hachage et arrêtez-vous si vous trouvez la première clé avec un entrée.

Je réponds à “Trouver un élément en double dans un tableau?”

Vous recherchez i et j de 0 à

 for (int i=0; i 

Régler à plusieurs resockets dup = false est un non-sens. Dup est toujours faux ou il était vrai, alors vous avez laissé le code avec 'return'.

Écrire les réponses précédentes en code réel (Java):

Temps O (n log n):

  Arrays.sort(arr); for (int i = 1; i < arr.length; i++) if (arr[i] == arr[i - 1]) return arr[i]; throw new Exception(); // error: no duplicate 

À temps:

  Set set = new HashSet(); for (int i = 0; i < arr.length; i++) { if (set.contains(arr[i])) return arr[i]; set.add(arr[i]); } throw new Exception(); // error: no duplicate 

Référence java.util.TreeSet qui est implémenté arbre rouge-noir sous-jacent, c’est O (n * log (n)) .

Je recommande d’utiliser la carte de hachage (en supposant qu’il n’y ait pas de collision) pour le résoudre.

  private boolean hasDuplicate(int[] arr) { Map map = new HashMap(); // find the duplicate element from an array using map for (int i = 0; i < arr.length; i++) { if(map.containsKey(arr[i])) { return true; } else { map.put(arr[i], true); } } return false; } 

Complexité temporelle: O (n)

Complexité de l'espace: O (n)

Une autre approche consiste à sortinger et à comparer, mais le sorting ajoute des frais généraux supplémentaires .

En utilisant des collections, nous pouvons utiliser l’extrait de code ci-dessous –

 Set set = new HashSet(); for (Ssortingng arrayElement : arr) { if (!set.add(arrayElement)) { System.out.println("Duplicate Element is : " + arrayElement); } } 

Trouvez la solution de complexité O (n) ci-dessous –

 int ar[]={0,1,2,3,0,2,3,1,0,2}; Set mySet=new HashSet<>(); for(int n:ar){ if(!mySet.add(n)){ System.out.println(" "+n); } } 

Et un autre processus moins complexe en espace O (N) et éventuellement O (n Log n) –

  public void duplicateElementSolution(int ar[]){ Arrays.sort(ar); for(int i=0;i<(ar.length-1);i++){ if(ar[i]==ar[i+1]){ System.out.println(" "+ar[i]); } } } 

(La question dans sa forme actuelle est un peu déroutante – ma réponse suppose que la question concerne la recherche de deux nombres dans un tableau qui totalisent une valeur donnée)

Étant donné que le tableau donné n’est pas sortingé, je suppose que nous ne sums pas autorisés à sortinger le tableau (c’est-à-dire que l’ordre donné du tableau ne peut pas être modifié).

La solution la plus simple, à mon humble avis, consiste à parcourir chaque nombre x et à vérifier si Ix apparaît n’importe où dans les tableaux. C’est essentiellement ce que fait votre solution O (n ^ 2).

Cela peut être réduit à O (n) ou à O (nlogn) en accélérant la recherche à l’aide d’une sorte de structure de données à définition rapide. En gros, lorsque nous parcourons le tableau, nous interrogeons pour voir si Ix se produit dans l’ensemble.

Code (en Python):

 l=[1,2,3,4,5,6,7,8,9] seen=set() I=11 for item in l: if I-item in seen: print "(%d,%d)"%(item,I-item) seen.add(item) 

La complexité de la solution dépend de la complexité d’insertion / recherche de la structure de données set que vous utilisez. Une implémentation basée sur une table de hachage a une complexité O (1), elle vous donne donc un algorithme O (n), tandis qu’un set basé set une arborescence génère un algorithme O (nlogn).

Modifier:

La structure de données équivalente à l’ set Python serait stl::set en C ++ et TreeSet / HashSet en Java. La ligne Ix in seen se traduirait par seen.contains(Ix) en Java et seen.find(Ix)==seen.end() en C ++.