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:

  1. Recherche séquentielle
  2. 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 (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