Comparer deux tableaux ou arrays, trouver des valeurs similaires et différentes

J'ai deux tableaux (ou tableaux si c'est plus facile) de chaînes. J'ai besoin de comparer ceux-ci, trouver qui existent seulement dans le premier tableau, qui existent dans les deux, et qui existent seulement dans le second tableau. Ces tableaux ont des longueurs différentes et peuvent être dans des ordres différents. Si nécessaire, je suppose que je pourrais les trier ...Comparer deux tableaux ou arrays, trouver des valeurs similaires et différentes

Je sais que je pourrais bidouiller ceci ensemble, mais je pense que ceci pourrait avoir une solution assez standard et efficace/"meilleure", et je suis curieux plus que n'importe quoi. J'utilise C# pour cela, mais si vous voulez écrire votre solution dans une autre langue, toute aide est la bienvenue.

Merci pour l'aide!

Source

2010-07-19 Wes

Les devoirs par hasard? –

Jetez un oeil sur les échantillons Linq 101 ici, ils devraient aider (en particulier les opérateurs ensemble): http://msdn.microsoft.com/en-us/vcsharp/aa336746.aspx – andyp

Non ce n'est pas devoirs haha. Je sais juste qu'il y a un moyen plus cool/plus efficace que ce que je pourrais trouver dans environ 20 minutes. Je n'ai jamais utilisé Linq auparavant, mais c'est peut-être le moment idéal pour y plonger. Merci pour la suggestion. – Wes

var onlyinfirst = from s in list1 where !list2.Contains(s) select s; 
var onlyinsecond = from s in list2 where !list1.Contains(s) select s; 
var onboth = from s in list1 where list2.Contains(s) select s;

Source

2010-07-19 19:24:59 Luiscencio

C'est ce que j'avais imaginé. Je me suis juste dit qu'il y avait une bonne façon de le faire en utilisant des comparables ou quelque chose. Je vais aussi essayer le linq, mais si tout le reste échoue, cela fonctionnera. – Wes

Notez que si les listes sont de taille n et m alors ces solutions sont toutes O (n * m). Il existe des solutions beaucoup plus efficaces si m et n sont grands. –

Si les baies sont grandes, vous devez utiliser une structure de données efficace pour ces opérations; les tableaux ne le sont pas.

La solution naïve est O (n^2) dans le temps si les tableaux sont de taille n.

Si vous triez les tableaux en place, vous pouvez les rechercher en mode binaire; le tri sera probablement O (n lg n) et chercher n fois à un coût de lg n par recherche sera également O (n lg n) dans le temps.

Si vous tournez d'abord chaque matrice dans un HashSet<T>, vous pouvez le faire en temps O (n) et O (n) en espace supplémentaire.

Source

2010-07-19 19:35:55

Je n'ai jamais utilisé un hashset mais je suis très curieux, je vais y jeter un coup d'oeil, merci! – Wes

@Wes: 'HashSet' a été introduit dans .NET Framework 3.5. – Brian

@Wes: @Brian: Et il a été appelé HashSet au lieu du nom plus sensible "Set" parce que ... attendez-le ... car "Set" est * un mot-clé de Visual Basic *. –

Comparer deux tableaux ou arrays, trouver des valeurs similaires et différentes

Répondre

Questions connexes