Nombre manquant(s) Question d'Entrevue Redux
La commune interview problème de la détermination de la valeur manquante dans une gamme allant de 1 à N a été fait mille fois. Les Variations incluent des 2 valeurs manquantes jusqu'à K valeurs manquantes.
Exemple de problème: Gamme [1,10] (1 2 4 5 7 8 9 10) = {3,6}
Voici un exemple des différentes solutions:
Ma question est que vu que le cas simple d'une valeur manquante est de O(n) la complexité et de la complexité de la plus grande des cas convergent à peu près quelque chose de plus grand que O(nlogn):
Ne pourrait-elle pas être plus facile de répondre à la question en disant sorte (mergesort) la plage et itérer sur elle en observant les éléments manquants?
Cette solution ne devrait pas prendre plus de O(nlogn) et est capable de résoudre le problème pour les autres plages de 1 à N tel que de 10 à 1000 -100 à +100 etc...
Est-il une raison de croire que les solutions ci-dessus DONC, le lien sera mieux que le tri en fonction de la solution pour un plus grand nombre de valeurs manquantes?
Remarque: Il semble que beaucoup de la commune de solutions à ce problème, supposons qu'un seul numéro de l'approche de la théorie. Si l'on est invité à une telle question dans un S/E entrevue ne serait-il pas prudent d'utiliser une plus informatique/algorithmique approche, en supposant que l'approche est sur le pair avec le nombre de théorie de la complexité de la solution,...
Plus de liens relatifs:
- https://mathoverflow.net/questions/25374/duplicate-detection-problem
- Comment savoir si un tableau est une permutation en O(n)?
- De tri ou à l'aide de BitSets sont parfaitement solutions valables, à moins que l'enquêteur précise qu'il est à la recherche d'un streaming algorithme ou que le jeu nécessite trop de mémoire.
- Que faire si vous n'avez même pas O(N) de la mémoire disponible? Que faire si vous avez à mettre en œuvre ce sur un dispositif intégré avec des ressources très limitées, et l'entrée se présente sous la forme d'un flux sans accès aléatoire?
- Le problème avec cette réponse, c'est l'OP posté dans questions qui requièrent spécifiquement O(K) de l'espace; que cette réponse nécessite O(N) l'espace. L'OP caractérisé autres réponses (dont certains sont très bons) comme "ridicule réponses".
- Les problèmes faire le plus de sens, lorsque l'entrée est donnée dans un flux de sens: Vous ne pouvez pas stocker tous les
néléments en mémoire, mais ils sont affichées une à la fois. Vous n'avezk^O(1)de mémoire pour jouer avec. Dans ce cas, la somme des puissances technique n'a de sens. Vous pouvez également améliorer le "temps utilisé par le numéro indiqué", par hachage comme dans stackoverflow.com/a/36851791/205521
Vous devez vous connecter pour publier un commentaire.
Vous spécifiez uniquement le temps de la complexité, mais l'espace de la complexité est également importante à considérer.
Le problème de la complexité peuvent être spécifiées en terme de
N(la longueur de la plage), etK(le nombre d'éléments manquants).Dans la question, vous avez le lien de la solution à l'aide d'équations est O(K) dans l'espace (ou peut-être un peu plus ?), comme vous avez besoin d'une équation par valeur inconnue.
Il y a aussi la préservation point: pouvez-vous modifier la liste des éléments connus ? Dans un certain nombre de cas, ce n'est pas souhaitable, et dans ce cas toute solution impliquant la réorganisation des éléments ou de les consommer, doit d'abord faire une copie, O(N-K) dans l'espace.
Je ne vois pas plus rapide qu'un linéaire de la solution: vous avez besoin de lire tous les éléments connus (N-K) et de sortie tous les éléments inconnus (K). Par conséquent, vous ne pouvez pas faire mieux que O(N) dans le temps.
Laissez-nous briser les solutions
Personnellement, bien que je trouve le équation du système solution intelligente, je serais probablement utiliser une des solutions de tri. Avouons-le: ils sont beaucoup plus simple à coder, en particulier le comptage, le tri un!
Et dans la mesure que le temps passe, dans une exécution réelle, je pense que le "comptage de tri" a battu toutes les autres solutions de mains vers le bas.
Note: le comptage, le tri ne nécessite pas de la plage à
[0, X), toute la gamme va faire, comme toute gamme finie peut être transposé à la[0, X)forme par une simple traduction.MODIFIER:
Changé le tri en O(N), on a besoin d'avoir tous les éléments disponibles pour les trier.
Avoir eu le temps de réfléchir sur le problème, j'ai aussi une autre solution à proposer. Comme indiqué, lorsque N augmente (spectaculaire) l'espace nécessaire pourrait exploser. Toutefois, si K est petit, alors nous pourrions changer notre représentation de la liste, à l'aide d'intervalles:
{4, 5, 3, 1, 7}peut être représenté comme
[1,1] U [3,5] U [7,7]Dans la moyenne des cas, le maintien d'une liste triée d'intervalles est beaucoup moins coûteuse que le maintien d'une liste triée des éléments, et il est facile d'en déduire les nombres manquants trop.
La complexité du temps est facile: O(N log N), après tout il s'agit essentiellement d'une insertion de tri.
Bien sûr, ce qui est vraiment intéressant, c'est qu'il n'est pas nécessaire de stocker la liste, donc vous pouvez le nourrir avec un flux de données de l'algorithme.
D'autre part, j'ai un moment difficile de déterminer la moyenne de l'espace de la complexité. La "finale" de l'espace occupé est O(K) (au plus K+1 intervalles), mais lors de la construction, il y aura beaucoup plus manquer les intervalles que nous introduisons les éléments dans aucun ordre particulier.
Le pire des cas est assez facile: N/2 intervalles (pensez bizarre vs le même nombre). Je ne peux cependant trouver le moyen de bien. Mon instinct me dit qu'il devrait être meilleure que O(N), mais je ne suis pas confiant.
Parce que les chiffres sont prises à partir d'une petite gamme finie, ils peuvent être "triés" en temps linéaire.
Tout ce que nous faisons est d'initialiser un tableau de 100 booléens, et, pour chaque entrée, définissez le booléen correspondant à chaque nombre dans l'entrée, puis étape par le biais de reporting les unset les booléens.
Si il existe au total N éléments où chaque nombre x est telle que 1 <= x <= N alors nous pouvons résoudre ce dans O(nlogn) temps de la complexité et de O(1) l'espace de la complexité.
Temps, la complexité est en O(nlogn)+O(n) presque égale à O(nlogn) quand N > 100.
Si la solution est théoriquement meilleur que le tri dépend de N et de K. Alors que votre solution est la complexité de
O(N*log(N)), la solution donnée estO(N*K). Je pense que la solution donnée est (le même que le tri solution) capable de résoudre n'importe quelle gamme[A, B]seulement par la transformation de la gamme[A, B]à[1, N].Quoi à ce sujet?
Ce qui est à gauche de votre ensemble sont les numéros manquants.
Si la plage est donné à vous, bien à l'avance, dans ce cas, la gamme est [1,10] vous pouvez effectuer l'opération XOR avec votre gamme et les chiffres donnés pour vous. Depuis XOR est opération commutative. Vous serez à gauche avec {3,6}
(1 2 3 4 5 6 7 8 9 10) XOR (1 2 4 5 7 8 9 10) ={3,6}