Trouver des doublons en temps o (n) et l’espace o (1)

Question

Entrée : Étant donné un tableau de n éléments qui contient les éléments de 0 à n-1, avec n’importe lequel de ces nombres qui apparaissent de nombreuses fois.

Objectif : Trouver ces répéter les numéros en o (n) et en utilisant uniquement des espaces mémoire constante.

Par exemple, soit n 7 et tableau {1, 2, 3, 1, 3, 0, 6}, la réponse devrait être 1 & 3. J’ai vérifié ici des questions similaires, mais les réponses utilisé certaines structures de données comme `` etc.

N’importe quel algorithme efficace pour la même chose ?

Answer 1

C'est ce que je suis venu avec, ce qui ne veut pas obtenir un autre bit de signe:

for i := 0 to n - 1
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 0 to n - 1
    if A[i] != i then 
        print A[i]
    end if
end for

La première boucle permute le tableau de sorte que si l'élément x est présent au moins une fois, puis une de ces inscriptions seront à la position A[x].

Notez qu'il peut ne pas sembler O(n) à première vue, mais il est - même si elle a une boucle imbriquée, il fonctionne encore en O(N) du temps. Un échange se produit uniquement si il y a un i tels que A[i] != i, et chaque swap définit au moins un élément tel que A[i] == i, alors que ce n'était pas le cas auparavant. Cela signifie que le nombre total de swaps (et donc le nombre total d'exécutions de l' while corps de boucle) est au plus N-1.

La deuxième boucle imprime les valeurs de x dont A[x] n'est pas égal à x - depuis la première boucle assure que, si x il existe au moins une fois dans le tableau, l'une de ces instances sera en A[x], cela signifie qu'il imprime les valeurs de x qui ne sont pas présents dans le tableau.

(Ideone lien de sorte que vous pouvez jouer avec elle)

Answer 2

la caf est génial réponse imprime chaque numéro qui apparaît à k fois dans le tableau k-1 fois. C'est utile de comportement, mais la question sans doute des appels pour chaque duplicata imprimé une seule fois, et il fait allusion à la possibilité de faire cela sans dépasser le temps linéaire/de la constante de l'espace de limites. Cela peut être fait en remplacement de son deuxième boucle avec le pseudo-code suivant:

for (i = 0; i < N; ++i) {
    if (A[i] != i && A[A[i]] == A[i]) {
        print A[i];
        A[A[i]] = i;
    }
}

Cela permet d'exploiter la propriété qu'après la première boucle s'exécute, si aucune valeur m apparaît plus d'une fois, une de ces apparitions est garanti d'être dans la bonne position, à savoir l' A[m]. Si nous sommes prudents, nous pouvons utiliser cette "maison" emplacement de stockage des informations quant à savoir si tous les doublons ont été imprimés ou non.

En fac de version, que nous sommes allés à travers le tableau, A[i] != i implicite qu' A[i] est un doublon. Dans ma version, je compte sur un peu différente, invariant: c' A[i] != i && A[A[i]] == A[i] implique qu' A[i] est un doublon que nous n'avons pas vu avant. (Si vous laissez tomber le "que nous n'avons pas vu avant," la partie, le reste peut être vu pour être implicites par la vérité de la caf de l'invariant, et la garantie que tous les doublons ont quelques copier dans la position d'origine.) Cette propriété détient au départ (après la caf de la 1ère boucle se termine) et je montre ci-dessous que c'est maintenu après chaque étape.

Comme nous passons par le tableau, le succès sur l' A[i] != i partie de l'épreuve implique qu' A[i] pourrait être un doublon qui n'a pas été vu avant. Si nous n'avons pas vu avant, puis nous nous attendons A[i]s'domicile à point à elle-même, c'est ce qui est testé par la deuxième moitié de l' if condition. Si c'est le cas, nous l'imprimer et de modifier l'emplacement du domicile au point de retour pour ce premier trouvé en double, la création d'un 2-step "cycle".

De voir que cette opération ne modifie pas notre invariant, supposons m = A[i] pour un poste particulier, i satisfaction A[i] != i && A[A[i]] == A[i]. Il est évident que le changement que nous faisons (A[A[i]] = i) sera à éviter à d'autres de les occurrences de m de sortie comme des doublons en causant de la 2e moitié de leur if conditions d'échouer, mais ça va fonctionner quand i arrive à l'emplacement du domicile, m? Oui, parce que maintenant, même si à ce nouveau i nous constatons que le 1er semestre de l' if condition, A[i] != i, est vrai, de la 2e moitié teste si l'endroit est un lieu d'accueil et constate qu'il ne l'est pas. Dans cette situation, on ne sait plus si m ou A[m] a été le double de la valeur, mais nous savons que de toute façon, il a déjà été signalé, car ces 2 cycles sont garantis de ne pas apparaître dans le résultat de la caf de la 1ère boucle. (Notez que si m != A[m] alors exactement l'une des m et A[m] plus d'une fois, et les autres ne se produit pas à tous.)

Answer 3

Voici le pseudo-code

Exemple de code en C++

Answer 4

"Où est-il question? Une interview?"

Je me souviens que j'ai eu un cas qui a impliqué des opérations sur un A[m][n] de la matrice, répartis en p processeurs, où j'ai besoin de sélectionner s meilleur des colonnes de chaque matrice locale, le swap colonnes avec tous les autres et répéter que, dans un arbre binaire de la mode. Bien sûr synchronisation a été un facteur clé j'ai donc été à l'aide d'un tableau d'indices de colonnes, de sorte que à la fin je pouvais me souvenir de ce qui les colonnes j'avais besoin de swap entre les processeurs.

Je crois que j'en étais arrivé à la même solution que dans la réponse de la caf mais de toute façon je n'ai pas pris assez de temps pour prouver que cela fonctionne vraiment, donc je suis finalement tombé en arrière à l'aide de O(n) l'espace.

Si, cela peut certainement se produire dans la pratique, en particulier lorsque vous utilisez des tableaux d'indices (parce qu'ils ont besoin de ne garder de 0 à n-1 valeurs).

(désolé pour l'affichage de cette comme une réponse, mais, assez drôle, je n'ai pas le privilège de poster un commentaire pour le moment)

Answer 5

Pour relativement petit N on peut utiliser les opérations div / mod

 n.times do |i|
  e = a[i]%n
  a[e] += n
end

n.times do |i| 
  count = a[i]/n
  puts i if count > 1
end
 

Pas C / C ++ mais de toute façon

http://ideone.com/GRZPI