trouver deux éléments a et b de l'ensemble A et B tels que lors de l'échange de ces éléments, la somme des ensembles est égale - algorithme, math

Ensemble A = [2, 10, 5, 9] = somme [A] 26

Ensemble B = [1, 10, 4, 9] = somme [B] 24

Trouvez deux éléments a, b des ensembles A et B tels que

somme [A] - a + b = somme [B] - b + a

J'ai résolu ce problème dans O (n ^ 2).

for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(sumOfA - A[i] + B[j] == sumOfB + A[i] - B[j]){
System.out.println("solution: " + A[i] + ", " + B[j])
return;
}
}
}

Comment cela peut-il être amélioré en O (n)?

Réponses:

Placez les éléments de l'ensemble A dans une structure permettant de tester l'appartenance à un ensemble dans O (1) (par exemple, une table de hachage ou un vecteur de bits si la plage d'éléments est petite). Cela fonctionnera dans O (n).

Maintenant, parcourez l'ensemble B et vérifiez s'il y a un élément dans A qui correspond à la distance correcte (la moitié de la différence des sommes) par rapport à l'élément dans B. Cela s'exécutera également dans O (n).

Voici un pseudo-code, où l'ensemble A est représenté de telle sorte que le contains l'opération s'exécute en O (1):

sumA = sum(A);
sumB = sum(B);
foreach (b in B) {
a = b + (sumA - sumB)/2;
if (A contains a) {
return pair(a, b);
}
}
return "no solution";