La façon la plus rapide de trouver 2 nombres manquants dans un tableau
Cette question n'existent que parce que de la pure curiosité. Pas de devoirs à faire.
Trouver le moyen le plus rapide pour trouver deux nombre manquant dans un tableau 1..n
Donc, Dans un related post: Le moyen le plus rapide pour trouver des disparus nombre dans un tableau de nombres
J'ai découvert que vous pouvez le faire assez rapidement en additionnant et soustrayant le total.
mais qu'en 2 chiffres?
Nos options sont les suivantes:
- Recherche séquentielle
- Résumant les éléments, soustrayant du total de tous les éléments à partir de 1..n, alors la recherche de tous les cas possibles.
Autre chose?
Possible d'avoir O(n) solution?
J'ai trouvé ça dans ruby section de l'un des sites web, mais n'importe quelle langue est considérée (à moins qu'il y a certaines choses pour une langue)
Vous pouvez simplement trier le tableau, ce qui peut être fait en O(n log n). Ensuite, vous pourriez en boucle sur les données triées et détecté si un certain nombre, je n'est pas suivi par n+1. Ce serait ajouter un autre n, mais serait encore en O(n log n).
-1. Votre question n'est pas claire. Que voulez-vous dire que les chiffres sont manquantes dans le tableau 1..n (probablement que vous vouliez dire
"Le plus rapide" est mal définie. Le plus rapide de l'algorithme et probablement plus rapide Ruby mise en œuvre, en double: stackoverflow.com/questions/3492302/.... Meilleur Ruby golfeur: peut-être steenslag de réponse.
-1. Votre question n'est pas claire. Que voulez-vous dire que les chiffres sont manquantes dans le tableau 1..n (probablement que vous vouliez dire
(1..n).to_a
)? N'est-ce pas inclure tous? Si il ya quelques détails sur le lien, il ne fonctionne toujours pas. Vous avez besoin de l'état de la question clairement ici."Le plus rapide" est mal définie. Le plus rapide de l'algorithme et probablement plus rapide Ruby mise en œuvre, en double: stackoverflow.com/questions/3492302/.... Meilleur Ruby golfeur: peut-être steenslag de réponse.
OriginalL'auteur user194076 | 2011-12-16
Vous devez vous connecter pour publier un commentaire.
La manière la plus simple (et très vite aussi:)
Ce n'est pas assez rapide, car il a une complexité quadratique, et il y en a connu et assez linéaire simple solution (voir la réponse ci-dessous).
OriginalL'auteur steenslag
S=a1+...+an
.T=a1*a1+...+an*an
.S'=1+...+n=n(n+1)/2
T'=1^2+...+n^2=n(n+1)(2n+1)/6
.x+y=S'-S
,x^2+y^2=T'-T
.x^2+y^2=(x+y)^2-2xy
=>xy=((S'-S)^2-(T'-T))/2
. Et maintenant, les chiffres sont simplement les racines de l'équation du second degré dansz
:z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0
.Question ouverte pour expliquer dernière étape: stackoverflow.com/questions/20026243/...
OriginalL'auteur Peteris
Assumer tableau [1,4,2,3,7] . Numéros manquants sont 5,6
Étape 1: Ajouter tous les nombres dans le tableau. 17. Nous savons que la somme de 1..7 ( n*(n+1)/2) = 28.
Donc de la forme x+y+17=28 => x+y=11
Étape 2: Multiplier tous les nombres dans le tableau. 168. Nous savons que le produit de la 1..7 = 5040.
Donc de la forme x*y*168 = 5040 => x*y=30
Nous avons x+y=11 et x-y=1. Résoudre pour x,y.
Cette solution ne marche pas nécessiter plus d'espace mémoire et se fait en O(n).
la multiplication peut facilement dépasser un Entier.MAX_VALUE
C'est très facile à comprendre.
OriginalL'auteur fragzilla
J'ai obtenu le temps le plus rapide parmi mes tests avec l'approche suivante (un peu plus rapide qu'avec la substitution de 2 tableaux):
OriginalL'auteur Aliaksei Kliuchnikau
Créer un ensemble de nombres de 1 à N. Calculer la différence de ce jeu avec l'ensemble des numéros du tableau. Comme les nombres sont distincts, le résultat sera le nombres manquants.
O(N)
le temps et l'espace.Utiliser les tables de hachage. Ou, puisque c'est un ensemble fini, tableaux de longueur N. les Deux sont des O(N).
OriginalL'auteur Michael J. Barber
Que faire si vous ne savez pas ce que les chiffres dans le tableau ont été? Si vous avez été seulement donné un tableau et dit qu'il était un certain nombre manquant, mais vous n'avez pas de connaissances de ce que les nombres étaient là, vous pouvez utiliser ceci:
length-1
? Sinon, qui est-à-dire qu'il n'est pas-10
ce qui manque?OriginalL'auteur mjd2
De sortie:
OriginalL'auteur Aman Kumar
Je propose la solution suivante
Méthode de bissection sur #Swift trouver 2 nombres manquants dans la gamme
OriginalL'auteur Sergey Sergeyev
OriginalL'auteur Grisha Kamyshnikov
J'aime l'idée de résumer et de comparer le résultat à la valeur attendue. Donc, mon idée est de diviser le tableau en parties égales, somme, ces et de voir si les deux côtés sont en manque d'un certain nombre. Si la moitié est correct, vous pouvez effectuer une itération sur l'autre moitié (contenant à la fois des numéros manquants..... cela semble donc erroné du point de vue linguistique >.<) jusqu'à ce que vous avez réussi à séparer les chiffres.
Cette approche est assez rapide si abs(i-j) est grand - ou en d'autres mots: lorsque les numéros manquants sont assez éloignés les uns des autres.
OriginalL'auteur yoshi