Question de l’entrevue: trois tableaux et O (N * N)

Question

Supposons que nous disposons de trois tableaux de longueur N qui contiennent un nombre arbitraire de type long. Puis on nous a donné un numéro de M (du même type), et notre mission est de choisir trois nombres A, B et C un de chaque tableau (en d'autres termes Un doit être choisi à partir de la première matrice, B de la deuxième et de C à partir de la troisième) de sorte que la somme A + B + C = M.

Question: pourrions-nous choisir tous les trois numéros et ils finissent avec le temps, la complexité de O(N²)?

---

Illustration:

Les tableaux sont:

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

Et M que nous avons reçu est 19. Ensuite, notre choix serait de 8 à partir de la première, 4 à partir de la deuxième et 7 de la troisième.

Answer 1

Cela peut être fait en O(1) et O(N²) de temps.

D'abord, permet de résoudre un simple problème:
Étant donné deux ensembles A et B choisir un seul élément de chaque sorte que leur somme est égale au nombre K.

Trier les deux tableaux qui prend O(NlogN).
Prendre des pointeurs i et j afin i points au début du tableau A et j de points à la fin de l' B.
Trouver la somme A[i] + B[j] et de la comparer avec d' K

• si A[i] + B[j] == K nous avons trouvé la paire A[i] et B[j]
• si A[i] + B[j] < K, nous avons besoin de augmentation de la somme, donc incrémenter i.
• si A[i] + B[j] > K, nous avons besoin de diminution de la somme, de sorte que la décrémentation j.

Ce processus de recherche de la paire après le tri prend O(N).

Maintenant, prenons le problème d'origine. Nous avons un troisième tableau appelle maintenant c' C.

Si l'algorithme est maintenant :

foreach element x in C
  find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x
end for

L'extérieur de la boucle s'exécute N temps et pour chaque essai, nous faisons un O(N) opérations de prise de l'ensemble de l'algorithme O(N²).

Answer 2

Vous pouvez le réduire au problème similaire avec deux tableaux, qui sont un peu célèbres et qui ont une solution simple O (n) (impliquant une itération des deux côtés).

1. Triez tous les tableaux.
2. Essayez chaque nombre A du premier tableau une fois.
3. Recherchez si les deux derniers tableaux peuvent nous donner des nombres B et C , tels que B + C = M - A .

Les étapes 2 et 3 multipliées nous donnent une complexité O (n ^ 2).

Answer 3

Les autres solutions sont déjà meilleures, mais voici quand même ma solution de temps O (n ^ 2) et de mémoire O (n).

Insère tous les éléments du tableau C dans une table de hachage. (complexité temporelle O (n), espace O (n)) Prenez toutes les paires (a, b), a de A et b de B (complexité temporelle O (n ^ 2)). Pour chaque paire, vérifiez si M- (a + b) existe dans l'hastable (complexité O (1) attendue par requête).

La complexité temporelle globale est donc O (n ^ 2) et la complexité spatiale de O (n) pour la table de hachage.

Answer 4

Hache la dernière liste. Le temps nécessaire pour le faire est O (N) sur cette liste particulière, mais cela sera ajouté à la phase suivante.

La phase suivante consiste à créer une "matrice" des deux premières lignes de leurs sommes. Puis regardez dans le hash si leur numéro correspondant est là. La création de la matrice est O (N * N) alors que regarder dans le hachage est un temps constant.

Answer 5

J'ai une solution. Insérer tous les éléments de la liste dans une table de hachage. Ce ne sera pas prendre en O(n) fois.

Une fois que c'est terminé, vous trouverez toutes les paires dans le reste des 2 tableaux et de voir si leur somme est présent dans la table de hachage.

En raison de hachage de branchement est constante, nous obtenons une équation de temps au total.

En utilisant cette approche, vous gagner du temps sur le tri.

Une autre idée est que si vous savez la taille maximale de chaque élément, vous pouvez utiliser une variation de seau de tri et de le faire en nlogn temps.