znajdź dwa elementy aib ze zbioru A i B w taki sposób, że przy zamianie tych elementów suma zbiorów jest równa - algorytm, matematyka

Ustaw A = [2, 10, 5, 9] = suma [A] 26

Zbiór B = [1, 10, 4, 9] = suma [B] 24

Znajdź dwa elementy a, b z zestawu A i B w taki sposób

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

Rozwiązałem ten problem w 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;
}
}
}

Jak można go ulepszyć do O (n)?

Odpowiedzi:

Umieść elementy zbioru A w strukturze, która pozwala przetestować zestaw członów w O (1) (na przykład tablica asocjacyjna lub wektor bitowy, jeśli zakres elementów jest mały). To będzie działać w O (n).

Teraz przejrzyj zbiór B i sprawdź, czy w elemencie A znajduje się poprawna odległość (połowa różnicy sum) od elementu w B. To również będzie działać w O (n).

Oto pseudo kod, w którym zestaw A jest reprezentowany w taki sposób, że contains operacja działa w 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";