Un élément qui diffère dans deux tableaux. Comment le trouver efficacement?

22

Je me prépare pour une entrevue de codage et je n'arrive pas vraiment à trouver le moyen le plus efficace de résoudre ce problème.

Disons que nous avons deux tableaux composés de nombres qui ne sont pas triés. Le tableau 2 contient un nombre que le tableau 1 ne contient pas. Les deux tableaux ont des nombres situés au hasard, pas nécessairement dans le même ordre ou aux mêmes indices. Par exemple:

Tableau 1 [78,11, 143, 84, 77, 1, 26, 35 .... n]

Tableau 2 [11,84, 35, 25, 77, 78, 26, 143 ... 21 ... n + 1]

Quel est l'algorithme le plus rapide pour trouver le nombre qui diffère? Quelle est sa durée de fonctionnement? Dans cet exemple, le nombre que nous recherchons est 21.

Mon idée était de parcourir le tableau 1 et de supprimer cette valeur du tableau 2. Répéter jusqu'à ce que vous ayez terminé. Cela devrait être autour du temps d'exécution , non?O(nlogn)

Konstantino Sparakis
la source
@Jandvorak Merci les gars pour les réponses. Je me suis levé tard et je me suis endormi après avoir posté ça. Le tableau n'est pas trié et tous les éléments apparaissent à des index aléatoires dans les deux tableaux.
Konstantino Sparakis
@KonstantinoSparakis: cette clarification invalide les réponses qui supposent que les deux tableaux contiennent les éléments dans les mêmes positions.
Mario Cervera
La publication croisée est désapprouvée par softwareengineering.stackexchange.com/users/256931/…
paparazzo
@Paparazzi cherchait simplement une solution que j'ai lue dans l'ingénierie du méta-logiciel était où aller pour obtenir une solution mais à l'époque je ne connaissais pas le forum CS. J'ai notifié les mods, pour le nettoyer.
Konstantino Sparakis
@Paparazzi existe-t-il un méta-post qui le confirme? Personnellement, je ne vois aucun moyen de bien mettre en œuvre cette politique.
djechlin

Réponses:

30

Je vois quatre façons principales de résoudre ce problème, avec des durées de fonctionnement différentes:

  • nO(n2)Solution : ce serait la solution que vous proposez. Notez que, comme les tableaux ne sont pas triés, la suppression prend un temps linéaire. Vous effectuez suppressions; par conséquent, cet algorithme prend un temps quadratique.n

  • O ( nO(nlogn)Solution : triez préalablement les tableaux; ensuite, effectuez une recherche linéaire pour identifier l'élément distinct. Dans cette solution, le temps d'exécution est dominé par l'opération de tri, d'où la borne supérieure .O(nlogn)

Lorsque vous identifiez une solution à un problème, vous devez toujours vous demander: puis-je faire mieux? Dans ce cas, vous pouvez, en faisant un usage intelligent des structures de données. Notez que tout ce que vous devez faire est d'itérer un tableau et d'effectuer des recherches répétées dans l'autre tableau. Quelle structure de données vous permet d'effectuer des recherches en temps constant (prévu)? Vous avez deviné à droite: une table de hachage .

  • O(n)Solution (attendue): itérer le premier tableau et stocker les éléments dans une table de hachage; puis effectuez un balayage linéaire dans le deuxième tableau, en recherchant chaque élément de la table de hachage. Renvoie l'élément qui ne se trouve pas dans la table de hachage. Cette solution à temps linéaire fonctionne pour tout type d'élément que vous pouvez passer à une fonction de hachage (par exemple, cela fonctionnerait de la même manière pour les tableaux de chaînes).

Si vous voulez des garanties de limite supérieure et que les tableaux sont strictement composés d'entiers, la meilleure solution est probablement celle proposée par Tobi Alafin (même si cette solution ne vous donnera pas l'index de l'élément qui diffère dans le second tableau) :

  • O(n)Solution (garantie): résumer les éléments du premier tableau. Ensuite, résumez les éléments du deuxième tableau. Enfin, effectuez la soustraction. Notez que cette solution peut en fait être généralisée à tout type de données dont les valeurs peuvent être représentées sous forme de chaînes de bits de longueur fixe, grâce à l' opérateur XOR au niveau du bit . Cela est expliqué en détail dans la réponse d' Ilmari Karonen .

Enfin, une autre possibilité (sous la même hypothèse de tableaux entiers) serait d'utiliser un algortihm de tri linéaire comme le comptage. Cela réduirait le temps d'exécution de la solution basée sur le tri de à .O ( n )O(nlogn)O(n)

Mario Cervera
la source
4
cependant, la sommation n'est pas linéaire si les nombres deviennent suffisamment grands.
Sarge Borsch
9
Une bonne chose à propos de l'algorithme de sommation est qu'il fonctionne avec n'importe quel groupe abélien, pas seulement avec des entiers (notamment uint64; cc @sarge).
John Dvorak
6
@Abdul, le problème est que si vos entiers sont très grands, vous ne pouvez plus prétendre qu'ils prennent pour être ajoutés. Je crois que la complexité devient si vous en tenez compte. L'utilisation de XOR au lieu de l'addition ordinaire résout cela, cependant, tout en permettant un nombre arbitrairement élevé en entrée. O ( n ln n )O(n)O(nlnn)
John Dvorak
2
@JanDvorak Non, ce n'est pas le cas. Vous supposez que l'opération définie sur le groupe abélien prend un temps constant. Cela ne peut pas simplement être supposé.
UTF-8
2
@ UTF-8 Je ne suppose pas cela. Mais il le fait dans des groupes finis (uint64), et l'addition sur place au niveau des chiffres (addition dans ) est de taille linéaire de l'opérande hors place. Ainsi, le calcul de la somme dans de tels groupes est un temps linéaire dans la taille totale des opérandes. Znd
John Dvorak
16

LeΘ(n)

  • abab
  • a(bc)=(ab)c
  • ab=ba
  • (ab)b=anO(n)

(Si le type ne peut prendre qu'un nombre fini de valeurs distinctes, ces propriétés sont suffisantes pour en faire un groupe abélien ; même si ce n'est pas le cas, ce sera au moins un semi-groupe annulatif commutatif .)

a=(a1,a2,,an)

(a)=a1a2an.
b=(b1,b2,,bn,bn+1)ax(b)=(a)x
x=(b)(a).

Plus généralement, nous pouvons même appliquer la méthode XOR au niveau du bit à des chaînes de longueur variable, en les remplissant jusqu'à la même longueur que nécessaire, tant que nous avons un moyen de supprimer de manière réversible le remplissage à la fin.

Dans certains cas, c'est trivial. Par exemple, les chaînes d'octets terminées par N de style C codent implicitement leur propre longueur, donc appliquer cette méthode pour elles est trivial: lorsque XORing deux chaînes, remplissez la plus courte avec des octets nuls pour que leur longueur corresponde, et coupez toutes les null finales supplémentaires de le résultat final. Notez que les chaînes de somme XOR intermédiaires peuvent contenir des octets nuls, cependant, vous devrez donc stocker leur longueur explicitement (mais vous n'en aurez besoin que d'un ou deux au maximum).

1001232octets de long, nous pourrions encoder la longueur de chaque chaîne sous forme d'entier 32 bits et l'ajouter à la chaîne. Ou nous pourrions même encoder des longueurs de chaînes arbitraires en utilisant un code de préfixe et les ajouter aux chaînes. Il existe également d'autres codages possibles.

Θ(n)

La seule partie potentiellement délicate est que, pour que l'annulation fonctionne, nous devons choisir une représentation de chaîne de bits canonique unique pour chaque valeur, ce qui pourrait être difficile (en fait, potentiellement même indécidable sur le plan des calculs) si les valeurs d'entrée dans les deux tableaux peuvent être données dans différentes représentations équivalentes. Ce n'est cependant pas une faiblesse spécifique de cette méthode; toute autre méthode de résolution de ce problème peut également échouer si l'entrée est autorisée à contenir des valeurs dont l'équivalence est indécidable.

Ilmari Karonen
la source
Wow très intéressant à prendre sur ce point. Merci @IlmariKaronen
Konstantino Sparakis
14

Je posterais cela comme un commentaire sur la réponse de Tobi, mais je n'ai pas encore la réputation.

Comme alternative au calcul de la somme de chaque liste (surtout s'il s'agit de grandes listes ou contenant de très grands nombres qui pourraient déborder votre type de données lors de la sommation), vous pouvez utiliser xor à la place.

Calculez simplement la somme xor (c'est-à-dire x [0] ^ x [1] ^ x [2] ... x [n]) de chaque liste, puis xor ces deux valeurs. Cela vous donnera la valeur de l'élément étranger (mais pas l'index).

C'est toujours O (n) et évite tout problème de débordement.

reffu
la source
3
J'utiliserais également XOR, car cela semble un peu plus propre, mais pour être honnête, le débordement n'est pas vraiment un problème tant que le langage que vous implémentez dans prend en charge le débordement en encapsulant.
Martin Ender
14

Element = Sum (Array2) - Sum (Array1)

Je doute sincèrement que ce soit l'algorithme le plus optimal. Mais c'est une autre façon de résoudre le problème et c'est la façon la plus simple de le résoudre. J'espère que ça aide.

Si le nombre d'éléments ajoutés est supérieur à un, cela ne fonctionnera pas.

Ma réponse a la même complexité de temps d'exécution pour le meilleur, le pire et le cas moyen,

EDIT
Après réflexion, je pense que ma réponse est votre solution.

nn11=n12=n+11=n

2n121=1

2n1+1=2n

Θ(n)

EDIT:
En raison de certains problèmes avec les types de données, une somme XOR suggérée par reffu sera plus appropriée.

Tobi Alafin
la source
Notez que cette méthode peut ne pas donner une réponse précise si vos valeurs sont flottantes, car la somme des nombres peut introduire des erreurs d'arrondi. Cela fonctionnera pour les valeurs entières, à condition que soit a) votre type entier ait un comportement de bouclage bien défini en cas de débordement, soit b) vous stockez les sommes dans des variables d'un type suffisamment large pour qu'elles ne puissent pas déborder.
Ilmari Karonen
La classe "BigNum" de Ruby peut probablement gérer cela.
Tobi Alafin
Cela ne fonctionne absolument pas si votre tableau contient par exemple des chaînes, ou à peu près tout ce qui ne peut pas être ajouté de manière significative.
gnasher729
Ouais, j'ai réalisé. Qu'en est-il de l'utilisation de «XOR»? Cela fonctionnera-t-il pour les flotteurs?
Tobi Alafin
Oui et aussi des pointeurs et en général tout ce qui se compose d'un nombre fixe de bits. De nombreuses langues ne le supportent pas, mais ce n'est pas un problème fondamental. L'addition / soustraction modulaire fonctionnera dans les mêmes cas.
harold
1

En supposant que le tableau 2 a été créé en prenant le tableau 1 et en insérant un élément à une position aléatoire, ou que le tableau 1 a été créé en prenant le tableau 2 et en supprimant un élément aléatoire.

Si tous les éléments du tableau sont garantis pour être distincts, le temps est O (ln n). Vous comparez les éléments à l'emplacement n / 2. S'ils sont égaux, l'élément supplémentaire va de n / 2 + 1 à la fin du tableau, sinon il va de 0 à n / 2. Etc.

Si les éléments du tableau ne sont pas garantis comme étant distincts: vous pouvez avoir n fois le numéro 1 dans le tableau 1 et le numéro 2 inséré n'importe où dans le tableau 2. Dans ce cas, vous ne pouvez pas savoir où est le numéro 2 sans regarder du tout éléments de tableau. Donc O (n).

PS. Les exigences ayant changé, vérifiez dans votre bibliothèque ce qui est disponible. Sur macOS / iOS, vous créez un NSCountedSet, ajoutez tous les numéros du tableau 2, supprimez tous les numéros du tableau 1, et ce qui reste est tout ce qui se trouve dans le tableau 2 mais pas dans le tableau 1, sans s'appuyer sur l'affirmation qu'il y en a un de plus article.

gnasher729
la source
Cette réponse était parfaite, mais la question a été modifiée avec une nouvelle exigence qui invalide votre hypothèse.
Mario Cervera
Votre nouvelle réponse semble juste. Quelle est la complexité du temps.
Tobi Alafin
Eh bien, tout d'abord quel est le temps nécessaire pour écrire le code. C'est trivial. NSCountedSet utilise le hachage, donc la complexité temporelle est "généralement linéaire".
gnasher729
-1

var le plus court, le plus long;

Convertissez le plus court en une carte pour un référencement rapide et la boucle sur la plus longue jusqu'à ce que la valeur actuelle ne soit pas dans la carte.

Quelque chose comme ça en javascript:

if (arr1.length> arr2.length) {shortest = arr2; le plus long = arr1; } else {shortest = arr1; le plus long = arr2; }

var map = shortest.reduce (fonction (obj, valeur) {obj [valeur] = true; return obj;}, {});

var difference = longest.find (function (value) {return !!! map [value];});

Craig Hardcastle
la source
Les codes sans explication ne comptent pas comme une bonne réponse ici. Aussi pourquoi voudriez-vous utiliser !!! ?
Evil
-1

Solution O (N) en complexité temporelle O (1) en termes de complexité spatiale

Énoncé du problème: en supposant que array2 contient tous les éléments de array1 plus un autre élément non présent dans array1.

La solution est: Nous utilisons xor pour trouver l'élément qui n'est pas présent dans array1 donc les étapes sont: 1. Commencez par array1 et faites xor de tous les éléments et stockez-les dans une variable. 2. Prenez le tableau2 et faites le xor de tous les éléments avec la variable qui stocke le xor de array1. 3. Après avoir fait l'opération, notre variable contiendra l'élément qui n'est présent que dans array2. L'algorithme ci-dessus fonctionne en raison de la propriété suivante de xor "a xor a = 0" "a xor 0 = a" J'espère que cela résout votre problème. Les solutions suggérées ci-dessus sont également très bien

Erreur stupide
la source