Le problème dit de supprimer les numéros de répétition. Ensuite, gardez les chiffres dans un tableau sans les autres répétés. Par exemple, [0, 0, 1, 1, 2, 2, 1, 1, 2, 2] serait [0, 1, 2], les nombres doivent être de la complexité de temps à temps Big O (n) et la complexité de l'espace O (1).
Jusqu'à présent, ce que j'ai est le numéro suivant en vérifiant le prochain. Il ne reçoit pas le nombre plus éloigné de celui-ci. Par exemple: [0, 1, 2, 3, 4, 5, 6, 2, 2, 8, 9] Le 2 est plus éloigné mais n'est pas vérifié par le code ci-dessous. D [i + 1] p>
Je ne peux pas utiliser la carte de hachage ou le jeu de hasch. P>
while (i < A.length) {
i++;
D = A;
if (i < A.length - 1) {
if (A[i] == D[i+1]){
B[i] = D[i + 1];
} else
A[i] = A[i];
}
}
3 Réponses :
plutôt que "vérifier la suivante", vous devez "vérifier tout précédent".
La question devient alors "Comment puis-je vérifier si un numéro existe dans un certain nombre d'autres éléments en temps constant"?
Utilisez un envisagez d'utiliser les deux méthodes Je laisse le code qui vous écrit ... hashset . Toutes les opérations d'une structure à base de hachage sont O (1).
ajouter () et contient () de hashset . .
Je ne peux pas utiliser une carte de hachage ou un jeu de hasch.
@Michele alors vous pouvez écrire votre propre
Et utiliser un ensemble de hachage / table supplémentaire entraînera une complexité spatiale de O (n) non constante.
Vous ne pouvez pas faire la tâche dans Ce n'est pas possible car dans l'ordre d'être supprimé, vous devez vérifier, qu'il existe un duplicata dans n'importe quelle position avant ou n'importe quelle position après la matrice.
Pour vérifier pour dupliquer, vous devez soit:
Donc, fondamentalement, vous devez échanger du temps pour espace, ou vice versa. O (n) heure et O (1) espace, si la matrice d'entrée n'est pas triée (et de vos mots - ce n'est pas ).
O (n ^ 2) temps de l'algorithme global)
SET (ceci conduira à O (n) temps et O (n) espace).
Ceci pourrait ne pas être possible avant et sauf si le tableau est trié avec une liste liée ou des éléments de marquage liés en tant qu'integer.min_value, "Espace et Time Trade off" appliquant ce directeur si nous avons besoin de temps plus rapide, alors nous devons échanger de l'espace et vice versa.
Devez-vous utiliser le même tableau ou pouvez-vous copier le résultat vers un nouveau tableau?
Je ne suis pas sûr que vous puissiez le faire dans O (n), tout ce que je peux penser, c'est comme O (n + 10) ou pire. La première solution qui me vient à l'esprit serait d'utiliser un tableau temporaire de taille 10. Puis itérale sur la matrice en question et d'incrémenter simplement le décalage de la valeur
++ . Ensuite, tout ce qui est dans la matrice de résultat qui n'est pas zéro est une valeur souhaitée, dans l'ordre. Le problème est que vous devez faire itérair la matrice de résultat menant à N + 10. Je suppose que «la complexité spatiale O (1)» signifie qu'il ne se développe pas avec la complexité de n, mais elle est plus grande que celle de N.Vous pouvez utiliser un tableau différent. C'est possible. C'est l'affectation des devoirs.
Si vous utilisez une table / jeu de hachage, vous pouvez suivre les numéros répétés et votre complexité amportisée sera O (N). Cependant, la complexité spatiale de O (1) signifie que vous ne pouvez utiliser aucune mémoire supplémentaire. Tri de la matrice sera O (n * journal n) et ne produira pas de sortie "stable" de [3 1 5], par exemple. Êtes-vous sûr de la complexité de l'espace?
J'ai oublié de dire que je ne peux pas utiliser une table de hachage. J'ai été expliqué qu'il y a deux pointeurs. Le premier vérifie la seconde. Ensuite, la droite se déplace si c'est correct. Les restes de gauche. La droite se déplace si c'est faux aussi. Fondamentalement, la gauche ne se déplace que lorsqu'il y a un nouveau nombre répété.
Êtes-vous autorisé à utiliser
System.ArrayCopyCopy ouArrays.copyOfrange ?Michelle, ce que vous mentionnez comme algorithme peut fonctionner dans O (N) uniquement si les doublons sont regroupés comme 222, 111, 555., 222 donneraient 2,1,5,2. Il sera dans O (n) et n'utilisera aucun stockage supplémentaire (même le résultat peut être maintenu en place). Toutefois, votre exemple exclua explicitement toutes les doubles emplois non seulement les en cluster. Vérifiez votre affectation avec soin
@Michele Deux pointeurs ne fonctionnera que si votre tableau est trié