Je cherche la manière la plus efficace de résoudre le problème suivant
Problème: P>
for i = 0 .. B.Lenghtt-1
{
for j= 0 .. A.Lenght-1
{
if A[j] == B[i]
A[j] = 0;
B[i] = 0;
break;
}
}
// B elemnts different from 0 are the Removed elements
// A elemnts different from 0 are the Added elemnts
7 Réponses :
Dans une sorte de code C ++ pseudo:
Le tri est votre ami.
Trier les deux tableaux (A et B), puis les marcher (en utilisant X et Y comme comptoirs). Descendre les deux 1 à la fois. Vous pouvez dériver tous vos tests de là:
(J'ai peut-être manqué une affaire Edge, mais vous obtenez l'idée générale.)
(éditer: le boîtier de bord principal qui n'est pas couvert ici est de manipuler lorsque vous atteignez la fin de l'un des tableaux avant l'autre, mais il n'est pas difficile de comprendre. :)
Merci Joe, Andreas et Kriss. Juste un chèque final, en termes d'efficacité est correct de dire que vos solutions coûte N) + n journal (n) + n = O (n log n), dans l'approche, ce type de problèmes est toujours recommandé à Trier d'abord, non? jj
@JJ: essentiellement oui, le tri avant est meilleur. Dans ce cas particulier, vous pouvez également éviter de trier à l'aide de hachage, car vous n'avez pas vraiment besoin de la commande mais que vous ne devez savoir que si l'article est ici ou non.
Je préférerais aussi les hachages pour la complexité inférieure theta (n) .
Joe et Andreas, comment avez-vous trouvé cet algorithme? Pouvez-vous perdre une lumière dans votre pensée et comment avez-vous identifié ces tableaux de tri et cette façon de numériser sera efficace? jj
Vous pouvez également utiliser un dictionnaire Le dictionnaire final vous indique quels éléments ont été insérés / supprimés (et combien de fois). Cette solution devrait être assez rapide même pour les listes plus grandes - plus rapidement que le tri.
Si votre langue en tant que multiset est disponible (définie avec le nombre d'éléments) Votre question est une opération standard.
B = multiset(Before) A = multiset(After)
Perl: résultat:
Ce n'est pas une entrée de golf de code! Sérieusement, Perl est cryptique au mieux, utilisez une langue (ou un pseudo-code) plus facile pour illustrer un algorithme que vous souhaitez partager. J'ai du mal à comprendre ce que vous faites ici même si le problème est trivial.
Ceci peut être résolu en temps linéaire.
Créez une carte pour calculer le nombre de répétitions de chaque élément.
Passez à travers le Voici un code Java pour cela (non testé, juste écrit maintenant): < / p> avant tableau et remplissez la carte.
Parcourez le tableau après et diminuez la valeur dans la carte pour chaque élément.
À la fin, passez par la carte et si vous trouvez une valeur négative, cet élément a été ajouté - si positif, cet élément a été supprimé.
dans groovy: résultat: pour dans groovy Je me réfère également Groovy Collection API glisse de Trygve Amundsen avec une très bonne table avec des méthodes fonctionnelles Deuxième solution: comteby Je suis d'aperçu de injecter est comme réduire dans d'autres langages fonctionnelles.
Si 3, 8 sont ajoutés et 7, 2, 1 sont supprimés alors le "tableau après" doit être
{3, 8, 8} ou{1, 3, 8, 8} < / code>.Un "1" ne peut pas exister dans le tableau "après". Vous commencez par un seul "1", vous le supprimez et vous ne l'ajoutez pas, alors pourquoi est-il là-bas dans le tableau après? Vous devriez corriger votre exemple.
Mes erreurs habituelles, je l'ai corrigée. Thx, jj