Comparez deux tableaux entiers de même longueur

Question

[Description] Étant donné deux tableaux entiers de même longueur. Concevez un algorithme qui peut juger s'ils sont identiques. La définition de «même» est que, si ces deux tableaux étaient triés, les éléments dans la position correspondante devraient être les mêmes.

 [Example]
<1 2 3 4>  = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>
 

[Limitation] L'algorithme doit nécessiter un espace supplémentaire constant et un temps d'exécution O (n).

Answer 1

(Probablement trop complexe pour une question d'entrevue.)

(Vous pouvez utiliser le temps O (N) pour vérifier que les valeurs min, max, sum, sumsq, etc. sont égales en premier.)

Utilisez le tri radix sans espace supplémentaire pour trier les deux tableaux en place. Complexité temporelle O (N), espace O (1).

Comparez-les ensuite à l'aide de l'algorithme habituel. Complexité temporelle O (N), espace O (1).

(Pourvu (max - min) des tableaux soit de O (N ^k ) avec un k fini.)

Answer 2

Vous pouvez essayer une approche probabiliste - convertir les tableaux dans un nombre énorme de base B et mod par certains, le premier P, par exemple somme B^a_i tous i mod certains grands-ish P. Si ils viennent tous deux vers le même numéro, essayez à nouveau pour un nombre de nombres premiers que vous voulez. Si c'est faux à toutes les tentatives, alors qu'ils ne sont pas correctes. Si ils passent suffisamment de défis, alors ils sont égaux, avec une forte probabilité.

Il y a un trivial preuve pour B > N, P > plus grand nombre. Donc il doit y avoir un défi qui ne peuvent être satisfaites. C'est en fait l'approche déterministe, bien que l'analyse de la complexité qui pourrait être plus difficile, en fonction de la façon dont les gens considèrent la complexité en termes de la taille de l'entrée (plutôt que de simplement le nombre d'éléments).

Answer 3

Je prétends que: à moins que la plage d'entrée ne soit spécifiée, il est IMPOSSIBLE de résoudre dans un espace supplémentaire instantané et le temps d'exécution O (n).

Je serai heureux d'avoir tort, afin que je puisse apprendre quelque chose de nouveau.

Answer 4

1. Insérez tous les éléments du premier tableau dans une table de hachage
2. Essayez d'insérer tous les éléments du deuxième tableau dans la même table de hachage - pour chaque insert à l'élément devrait déjà être là

Ok, ce n'est pas avec un espace supplémentaire constant, mais le mieux que j'ai pu trouver pour le moment :-). Y a-t-il d'autres contraintes imposées à la question, comme par exemple le plus grand entier qui peut être inclus dans le tableau?

Answer 5

Quelques réponses sont fondamentalement correcte, même si elles ne ressemblent pas à ça. La table de hachage approche (pour un exemple) a une limite supérieure en fonction de la plage de la type plutôt que le nombre d'éléments dans les tableaux. Au moins par la plupart des définitions, qui fait de l' (limite supérieure) à l'espace une constante, même si la constante peut être assez important.

En théorie, vous pouvez changer qu'à partir d'une limite supérieure à un véritable quantité constante de l'espace. Juste pour exemple, si vous travaillez en C ou C++, et c'était un tableau d' char, vous pouvez utiliser quelque chose comme:

size_t counts[UCHAR_MAX];

Depuis UCHAR_MAX est une constante, la quantité d'espace utilisé par le tableau est également une constante.

Edit: j'avais remarque pour que l'enregistrement d'un bond sur les plages/tailles des éléments impliqués est implicite dans presque toutes les descriptions de la complexité algorithmique. Juste pour exemple, nous tous savons que Quicksort est un O(N log N) de l'algorithme. C'est seulement vrai, cependant, si nous supposons que comparer et d'échanger sur les éléments en cours de tri prend à temps constant, qui ne peut être vrai que si nous avons lié la gamme. Si la gamme de produits en cause est suffisamment importante pour que l'on ne peut plus traiter une comparaison ou d'un swap que la prise constante de temps, puis sa complexité allait devenir quelque chose comme O(N log N log R), ont été R est la plage, de sorte log R se rapproche le nombre de bits nécessaire pour représenter un élément.