Dupliqué possible:
Question facile d'entrevue ont eu plus de difficulté: Numéros donnés 1..100, trouvez le (s) numéro (s) manquant (s)
Trouvez le manquant et Dupliquer des éléments dans un tableau en temps linéaire et espace constantJ'ai vu une question intéressante sur un forum.
Vous avez 100 éléments de 1 à 100 mais de byy erreur une de ces numéros a chevauché une autre en se répétant. Par exemple. 1,99,3, ..., 99 100 Le tableau n'est pas au format trié, comment trouver le numéro de répétition?
Je sais que le hash peut le faire O (n) l'espace et o (n) espace, j'ai besoin d'un (1) espace.
4 Réponses :
Nous pouvons le faire dans O (n) et espace constant:
index = math.abs (A [i]) - 1
- Vérifiez la valeur à
index
- S'il est positif, multipliez -1, c'est-à-dire le rendre négatif.
- Si c'est négatif, revenir (
index + 1 ) comme réponse, car cela signifie que nous avons vu cet index avant.
"" xxx
Mais que se passe-t-il si les valeurs de la matrice dépassent les limites de la matrice, par exemple 1000, 1001, 1002, 1000, ...
La question indique clairement que ses 1 à 100 et un élément est répété.
Yup - Je devrais lire plus attentivement: /
@schtaver Oui, cela ne fonctionnera pas pour cela, mais comme User973931 a déclaré que la question indique clairement que les chiffres sont de 1 à 100.
Vous stockez une information pour (potentiellement) chaque élément de votre contribution. Ce n'est pas un espace constant.
@Nick Vous comprendrez quelle est la complexité spatiale? :)
@ user973931 désolé, signifiait dire "espace constant", pas "O (n) espace" (édité).
@Nick Pourquoi vous pensez que son espace n'est pas constant? J'utilise le même tableau pour stocker -ve signe
@Manan vous utilisez toujours une quantité linéaire d'espace pour construire votre solution. Si votre jeu d'entrée est immuable, ou non accessible au hasard, ou ne prend pas en charge les entiers signés, vous devez donc créer ce tableau vous-même.
@NICK La réponse est applicable uniquement avec les contraintes données sur les questions .....
@Manan Aucune de ces contraintes (entrée signée modifiée avec un accès aléatoire à temps constant) a été explicitement donnée dans la question, de sorte que c'est un peu un étirement pour les assumer. Mais dans tous les cas, cela ne qualifie toujours pas d'algorithme d'espace constant. Ce n'est pas une question de combien d'octets dont vous avez besoin avec Malloc (); C'est une question de savoir combien d'informations vous devez enregistrer.
@Elkamina merci mais je pense que la question indique clairement que les chiffres sont B / W 1 à 100 et d'avoir exactement écrasé par une autre ... j'apprécierais si vous pouvez me corriger où je vais me tromper ... Merci encore
@Manan Votre solution nécessite de stocker n valeurs supplémentaires (n = 100 ici), car vous stockez index. Ce n'est pas une solution spatiale constante.
@Elkamina je pense que vous me t'avez tort, je ne stocke pas d'index .. L'index dans le code ci-dessus est une variable temporaire. Pour plus de clarté, j'ai posté le code ci-dessus
@Manan mais vous conservez toujours quelque chose. Votre algorithme est essentiellement un type de seau. Vos godets Dans ce cas sont les bits de panneau vacants dans votre réseau d'intrants. Mais c'est toujours un algorithme d'espace linéaire.
@Manan La ligne a [index] = -1 * a [index]; écrase l'entrée. C'est pourquoi les gens indiquent que cette solution n'est pas un espace constant.
@Elkamina, croyez-moi si vous exécutez mon code au-dessus de l'exemple donné [5 5 3 2 1] fonctionnera.
@Manan mes excuses. Oui, ça marche. Mais, puisque vous manchonnez la matrice, ce n'est toujours pas une solution O (n) valide.
@Manan laissez-moi vous donner un exemple où cela ne fonctionnera pas. Supposons que je travaille sur cet ordinateur de 7 bits étrange et que l'entrée est une matrice sur 7 bits. Essentiellement, vous supposez qu'il y a suffisamment de place pour stocker un peu d'informations supplémentaires.
@Elkamina ok ça ne fonctionnera pas là-bas ... mais pensez-vous que Summation fonctionnera .. Et si la somme est hors de portée? Pour ajouter à cela, vous faites aussi une somme des carrés :)
@Manan Vous n'avez pas besoin de stocker plusieurs sommes de plusieurs somme de carrés. Mais juste une instance de chacun. C'est différent d'un bit supplémentaire pour chaque numéro dans le tableau. Quoi qu'il en soit, voir la solution de Pengone ci-dessous. Il s'agit d'une solution la meilleure solution à ce problème.
Calculez deux sommes: somme et somme carrée.
Dans votre exemple: suppose y remplacé x dans la séquence. maintenant, résolve pour x & y. espace constant et o (n) temps. de l'équation: substitut cela dans la deuxième équation: Notez que Y ^ 2 annule et vous êtes laissé avec une équation linéaire avec un seul inconnu: y. Résolvez-le! Comment résoudre x et y
Cette réponse a 2 votes en baisse et aucun commentaire. Veuillez expliquer ce qui est incorrect ici pour que l'OP puisse se réfuter ou réviser et d'autres comprennent le problème (potentiel).
Comment résolvez-vous cela pour x & y?
est une somme carrée vraiment nécessaire, si la longueur de la matrice est 101 et il y a 100 valeurs uniques, vous résumez ces 100 valeurs uniques et obtenez 5050, le Supposons que la somme revienne comme étant 5149, vous savez instantanément que 99 ont été dupliqués, ce n'est pas dupliqué. Travaillez quand il y a plus d'un duplicates, mais la question ne mentionnait qu'une valeur répétée une fois.
La longueur de la matrice @seph est 100. Un numéro est répété, un chiffre est omis. Par conséquent, deux inconnues nécessitant deux équations.
Pourquoi quelqu'un pourvoirait-il une réponse correcte?
L'espace requis pour somme et sq_sum dépend de la taille d'entrée, c'est-à-dire pas un espace constant
Nouvelle approche. Laissez espace total: 4 (ou 3 si vous réutilisez Temps total: 7 passe (ou 3 Si vous faites des indices en même temps que la matrice et calculez donc m être le numéro manquant et r Soyez le numéro répété. En passant à travers la matrice une fois, laissez x être le résultat de xor ing les entrées du tableau avec les indices 1 à n . Alors x = m xor r . En particulier, ce n'est pas 0 . Laissez b être n'importe quel bit non nul de x (il vous suffit de choisir un, et on existe seulement depuis que x n'est pas 0 ). En passant par la matrice, laisse y être le résultat de xor ing des entrées du tableau et des indices 1 à n où le bit b est 0 et que z soit le résultat de xor ing les entrées du tableau et les indices 1 à n où le bit b est 1 . Puis y et z maintenez m et r , donc tout ce qui reste est de faire une passe finale pour voir laquelle est dans le tableau.
x pour b )
y et z en même temps.
o (1) espace et O (n) temps.
Es-tu sûr? Dans la première étape lente est N + 1. Alors tableau [lent] retourne une erreur ou des ordures, non?
Je pense toujours que ça ne marcherait pas. Considérons des cas où il y a plusieurs cycles. Ou considérez un cas où le tableau [N] = n.
Vous avez donc besoin d'un laissez-passer supplémentaire pour chaque morceau non nul de x droite? Dans ce cas, votre solution O (nlogn) à temps. Je ne suis pas très sûr de ce fait, mais s'il vous plaît faites le moi savoir.
@Elkamina Non, vous ne faites qu'une passe pour votre bit non nul préféré. Vous n'avez pas à le faire pour chaque bit non nul. Cela fonctionne pour tout bit non nul.
La taille de x dépend-elle de n? Si oui, alors ce n'est pas O (1) espace.
Calculer la somme de tous les entiers Calculer int p = somme% 100 100 - p est la réponse
Cela ne vous donnera que la différence entre le nombre manquant et le dupliqué, mais pas suffisant pour identifier l'un d'eux. Vous avez deux inconnus, vous avez besoin d'équations. Voir la réponse d'Elkamina ci-dessus.
C'est incorrect. Prenez deux cas: 5 est remplacé par 10 et 6 est remplacé par 11. Dans les deux cas, la somme sera la même.
Exemple 1,99,3,4 ... 100. Maintenant, la somme% 100 sera de 98. 100-98 est 2 :)
@topoder Dites-moi comment cela fonctionne pour le cas où 5 est remplacé par 20?
@topcoder I Get 1 + 99 + 3 + 4 + ... + 100% 100 = 47.
@topcoder que vous avez supprimé un 2 et ajouté un 99. La somme% 100 sera de 97.
@Nickbarnes La somme de 1 à 100 modulo 100 n'est pas 0. Pourquoi tout le monde pense-t-il que c'est? 1 + 2 + ... + 100 = 5050 !!
@Pengone Oups, tu as raison ... j'ai oublié de diviser n (n + 1) par 2 :)
Pourquoi avez-vous accepté une réponse incorrecte? (pas O (1) espace)