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

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(n \log n)$

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

• $O(n^2)$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 ( $O(n \: log \: n)$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(n \: log \: n)$

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(n \: log \: n)$$O(n)$

Le$\Theta(n)$$\oplus$

• $a$$b$$a \oplus b$$\oplus$
• $a \oplus (b \oplus c) = (a \oplus b) \oplus c$
• $a \oplus b = b \oplus a$
• $\ominus$$(a \oplus b) \ominus b = a$$n$${\rm O}(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 .)

$\oplus$$a = (a_1, a_2, \dots, a_n)$

$\oplus$$\ominus$$\oplus$$\ominus$

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).

$1$$0$$0$$1$$2^{32}$octets 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.

$\Theta(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.

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.

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.

$n$$n-1$$1 = n-1$$2 = n+1 -1=n$

$2n-1$$2 -$$1 = 1$

$2n - 1 + 1 = 2n$

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.

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.

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];});

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