Recherche d'un élément commun dans les tableaux

Question

Si j'ai des tableaux N, quelle est la meilleure façon de trouver les éléments communs (la complexité temporelle, l'espace n'est pas important). Vous pourriez juste trouver 1 élément et arrêter.

Editer: Les éléments sont tous des nombres.

Éditer: Ceux-ci ne sont pas triés. S'il vous plaît ne pas trier et numériser.

Ce n'est pas un problème de devoirs. Quelqu'un m'a posé cette question il y a longtemps. Il utilisait un hasch pour résoudre le problème et m'a demandé si j'avais un meilleur moyen.

Answer 1

La méthode la plus directe consiste à croiser les deux premières matrices, puis d'intersecter cette intersection avec les N-2 restantes. Si 'intersection' n'est pas défini dans la langue dans laquelle vous travaillez ou si vous avez besoin d'une réponse plus spécifique (vous avez besoin de la réponse 'comment faire l'intersection') alors modifiez votre question en tant que telle.

Sans tri, il n'y a pas de manière optimisée de faire cela en fonction des informations fournies. (ie trier et positionner tous les éléments l'un par rapport à l'autre, puis effectuer une itération sur la longueur des tableaux en vérifiant les éléments définis dans tous les tableaux)

Answer 2

Je commencerais par le cas dégénéré, en trouvant des éléments communs entre 2 matrices (plus sur cela plus tard). De là, je vais avoir une collection de valeurs communes que je vais utiliser comme un tableau lui-même et le comparer au tableau suivant. Cette vérification serait effectuée N-1 fois ou jusqu'à ce que le tableau "carry" d'éléments communs tombe à la taille 0.

On pourrait accélérer cela, j'imagine, en divisant-et-vaincre, en divisant les réseaux N dans les nœuds d'extrémité d'un arbre. Le niveau suivant de l'arbre est N/2 tableaux d'éléments communs, et ainsi de suite et ainsi de suite jusqu'à ce que vous avez un tableau en haut qui est rempli ou non. Dans les deux cas, vous auriez votre réponse. Sans tri et balayage, la meilleure vitesse opérationnelle que vous obtiendrez pour comparer 2 réseaux pour les éléments communs est O (N).

Answer 3

Créer un index de hachage, avec des éléments en tant que clés, compte comme des valeurs. Parcourez toutes les valeurs et mettez à jour le nombre dans l'index. Ensuite, parcourez l'index et vérifiez quels éléments ont count = N. La recherche d'un élément dans l'index doit être O (1), combinée à la boucle de tous les éléments M doit être O (M).

Si vous souhaitez conserver un ordre spécifique à une certaine matrice d'entrée, faites une boucle sur cette matrice et testez le nombre d'éléments dans l'index dans cet ordre.

Quelques cas particuliers:

si vous savez que les éléments sont des nombres entiers (positifs) avec un maximum qui est pas trop élevé, vous pouvez simplement utiliser un tableau normal comme indice « hachage » pour garder compte , où le nombre sont juste l'index de tableau.

J'ai supposé que dans chaque tableau chaque nombre se produit une seule fois. L'adapter pour plus d'occurrences devrait être facile (mettre le i-ème bit dans le compte pour le tableau i, ou seulement mettre à jour si l'élément courant compte == i-1).

EDIT Lorsque j'ai répondu à la question, la question n'a pas eu la partie "d'une meilleure façon" que le hachage.

Answer 4

La question posée est là une meilleure façon que le hachage. Il n'y a pas de meilleur moyen (c'est-à-dire une meilleure complexité temporelle) que de faire un hachage au fur et à mesure que chaque élément est typiquement constant. Les performances empiriques sont également favorables, en particulier si la plage de valeurs peut être mappée de un à un à un tableau en maintenant les chiffres. L'heure est alors proportionnelle au nombre d'éléments dans tous les tableaux. Le tri ne donnera pas une meilleure complexité, car il aura toujours besoin de visiter chaque élément au moins une fois, puis il y aura le journal N pour trier chaque tableau. Du point de vue des performances, vous obtiendrez les meilleures performances empiriques en ne traitant pas chaque baie entièrement, mais en traitant uniquement un bloc d'éléments de chaque matrice avant de passer au tableau suivant. Cela profitera du cache du processeur. Il en résulte également que moins d'éléments sont hachés dans des cas favorables lorsque des éléments communs apparaissent dans les mêmes régions du tableau (par exemple des éléments communs au début de tous les tableaux.) Le pire comportement n'est pas pire que de hacher chaque tableau. les éléments sont hachés.

Answer 5

Je ne pense pas que l'approche proposée par catchmeifyoutry fonctionnera.

Disons que vous avez deux tableaux 1: {1,1,2,3,4,5} 2: {1,3,6,7}

alors réponse devrait être 1 et 3 Mais si nous utilisons l'approche hashtable, j'en aurai 3 et nous ne trouverons jamais 1, dans sa situation.

également des problèmes devient plus complexe si nous avons entrée quelque chose comme ceci: 1: {1,1,1,2,3,4} 2: {1,1,5,6}

ici Je pense que nous devrions donner la production comme 1,1. L'approche suggérée échoue dans les deux cas.

Solution:

lu premier tableau et mis en Hashtable. Si nous retrouvons la même clé, n'incrémentez pas le compteur. Lire le deuxième tableau de la même manière. Maintenant, dans la table de hachage, nous avons des éléments communs qui comptent comme 2.

Mais encore une fois, cette approche échouera dans le second ensemble d'entrée que j'ai donné plus tôt.