Étant donné un tableau avec plusieurs entrées répétées, trouvez une entrée répétée O (N) time et espace constant

Nous avons reçu un tableau de taille N contenant des entiers compris entre 0 et N-2, les deux inclusivement.

Le tableau peut avoir plusieurs entrées répétées. Nous devons trouver l’une des entrées dupliquées dans le temps O (N) et l’espace constant.

Je pensais prendre le produit et la sum de tous les entiers du tableau, ainsi que le produit et la sum de tous les nombres compris entre 0 et N-2.

Ensuite, la différence des sums et la division des produits nous donneraient deux équations. Cette approche fonctionnerait si on supposait qu’il n’y avait que deux entrées répétées, mais comme il peut y en avoir plus de deux, je pense que mon approche échoue.

Aucune suggestion?

Edit: le tableau est immuable. Je me rends compte qu’il s’agit d’un élément d’information important et je m’excuse d’avoir oublié de l’inclure plus tôt.

Voici un bon traitement. Il passe par quelques problèmes plus faciles avant d’aborder celui-ci.

http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html

Il contient une solution pour quand vous pouvez modifier le tableau en entrée, et une autre pour quand vous ne pouvez pas.

Bref résumé au cas où le lien mourrait: les index du tableau vont de 0 .. N-1 et les valeurs du tableau vont de 0 .. N-2. Chaque élément de tableau peut donc être considéré comme un index (ou “pointeur”) dans le tableau lui-même: élément i “pointe sur” élément ra[i] , ra[i] pointe sur ra[ra[i]] et ainsi de suite. En suivant à plusieurs resockets ces indications, je dois éventuellement entrer dans un cycle, car nous ne pouvons certainement pas continuer indéfiniment sans revenir sur un nœud ou un autre.

Or, le tout dernier élément, N-1, n’est désigné par aucun autre élément. Donc, si nous commençons là et finissons par entrer dans un cycle, quelque part sur le parcours, il doit y avoir un élément accessible depuis deux endroits différents: l’itinéraire que nous avons emprunté pour la première fois et l’itinéraire faisant partie du cycle. Quelque chose comme ça:

  N-1 -> a1 -> a2 -> a3 ^ \ / v a6 <- a5 <- a4

Dans ce cas, a2 est accessible de deux endroits différents.

Mais un nœud qui est accessible depuis deux endroits différents est précisément ce que nous recherchons, un doublon dans le tableau (deux éléments de tableau différents contenant la même valeur).

La question est alors de savoir comment identifier a2, et la réponse consiste à utiliser l'algorithme de recherche de cycle de Floyd . En particulier, il nous indique le "début" de la boucle en temps O (N) et en espace O (1).

En supposant que nous puissions changer de tableau à la place, permutez chaque élément lorsque vous parcourez le tableau avec l’élément sur cette “position” (par exemple, si l’élément actuel est curr, échangez-le avec un [curr]) mais si un [curr] a déjà Curr alors vous savez que curr est un doublon.

 a = array... for i = 0; i < length(a); i++ curr = a[i] if a[curr] == curr: return duplicate curr swap(a[i], a[curr]) # Now a[curr] == curr and so if it happens again we know it is a duplicate.

Ce serait O (n) et l'espace constant.

Scannez le tableau et ajoutez chaque élément à un ensemble. Si l’élément existe déjà dans l’ensemble – vous avez une dupe.

Initialisez un tableau de bits de taille N-2 avec toutes les entrées à 0. Chaque index représente tous vos éléments dans la plage 0 à N-2.

Parcourez votre tableau et ajoutez des éléments à votre bitarray en définissant bitarray[number] == 1 . Si l’élément contient déjà un 1, alors vous avez déjà ajouté votre élément, revenez immédiatement.

Si vous arrivez à la fin de votre tableau sans trouver de doublon, retournez -1.

Inspiré par cette question SO, je pense que je choisirais d’abord de sortinger le tableau sur place en utilisant un algorithme qui est O (n) (bien que pas nécessairement rapide) trouvé dans wikipedia (de belles démos de sorting graphiques trouvées ici ), puis de passer en boucle. le tableau résultant pour trouver où le nombre suivant est égal au nombre actuel.

Essayez de penser avec d’autres structures de données. Certaines structures de données, comme un hachage, ne traverseront pas les éléments actuels lors de l’ajout ou de la recherche, ce qui conservera votre O (n).

 HashSet hSet = new HashSet(); for(int i = 0; i < array.length(); i++){ if(hSet.contains(array[i]) return array[i]; else hSet.add(array[i]); } return -1;

Bien que je ne sois pas sûr que cela satisfasse vos besoins en mémoire, le post précédent d’extraneon avec le sorting en place avec une deuxième traverse pourrait être plus que ce que vous recherchez

(désolé, je ne peux pas encore append de commentaires ….)

@Blastfurnace ah .. bonne prise que pour les boucles a besoin d’une vérification d’abord

 if a[i] == i: continue # Don't swap with yourself!

Si array est immuable, vous pouvez simplement continuer à suivre les éléments, c’est-à-dire sauter jusqu’à un [i] == i, puis d’un [i] à un [a [i]]. Cela créera une boucle et nous pourrons alors utiliser la solution “Comment détecter une boucle dans une liste chaînée” (gardez 2 pointeurs se déplaçant à la vitesse 1 sur 2 et quand ils se rencontreront, vous saurez que vous avez atteint le cycle).

Si nous pouvons changer un tableau et le renvoyer inchangé, nous pouvons sortingcher 🙂 À partir de i = 0, convertissons un [a [i]] en un entier négatif s’il ne l’est pas déjà, s’il est déjà négatif, alors nous soaps que l’élément a [i] a été visité deux fois. Avant de retourner, retournez tous les négatifs en positifs (pour 0, utilisez MIN_INT)