Znalezienie trzech elementów w tablicy, których suma jest najbliższa danej liczbie
Biorąc pod uwagę tablicę liczb całkowitych, A1, A2, ..., An, łącznie z negatywami i pozytywami oraz inną liczbą całkowitą S. Teraz musimy znaleźć trzy różne liczby całkowite w tablicy, których suma jest najbliższa podanej liczbie całkowitej S. Jeśli istnieje więcej niż jedno rozwiązanie, każde z nich jest w porządku.
Można założyć, że wszystkie liczby całkowite mieszczą się w przedziale int32_t i nie dojdzie do przepełnienia arytmetycznego przy obliczaniu sumy. S to nic specjalnego, ale losowo wybrany numer.
Czy istnieje jakiś skuteczny algorytm inny niż brute force search, aby znaleźć trzy liczby całkowite?
13 answers
Czy istnieje jakiś skuteczny algorytm inny niż brute force search, aby znaleźć trzy liczby całkowite?
Yep; możemy to rozwiązać W O (n2) Czas! Po pierwsze, zastanów się, czy twój problem P
może być sformułowany równoważnie w nieco inny sposób, który eliminuje potrzebę "wartości docelowej": {]}
Oryginalny problem
P
: czy z tablicyA
zn
liczb całkowitych i wartości docelowejS
istnieje 3-krotka zA
, która sumuje się doS
?Zmodyfikowany problem
P'
: biorąc pod uwagę tablicęA
zn
liczb całkowitych, czy istnieje krotka 3 zA
, która sumuje się do zera?
Zauważ, że możesz przejść od tej wersji problemu P'
z P
poprzez odjęcie S/3 od każdego elementu w A
, ale teraz nie potrzebujesz już wartości docelowej.
Oczywiście, jeśli po prostu przetestujemy wszystkie możliwe krotki 3, rozwiążemy problem w O (n3) -- to podstawa brutalnej siły. Na można zrobić lepiej? Co jeśli wybierzemy krotki w nieco mądrzejszy sposób?
Po pierwsze, inwestujemy trochę czasu, aby posortować tablicę, co kosztuje nas początkową karę w wysokości O (N log n). Teraz wykonujemy ten algorytm:
for (i in 1..n-2) {
j = i+1 // Start right after i.
k = n // Start at the end of the array.
while (k >= j) {
// We got a match! All done.
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
// We didn't match. Let's try to get a little closer:
// If the sum was too big, decrement k.
// If the sum was too small, increment j.
(A[i] + A[j] + A[k] > 0) ? k-- : j++
}
// When the while-loop finishes, j and k have passed each other and there's
// no more useful combinations that we can try with this i.
}
Algorytm ten działa poprzez umieszczenie trzech wskaźników, i
, j
, i k
w różnych punktach tablicy. i
zaczyna się na początku i powoli biegnie do końca. k
wskazuje na ostatni element. j
wskazuje gdzie i
mA zaczęło się od Iteracyjnie staramy się sumować elementy według ich odpowiednich indeksów i za każdym razem dzieje się jedna z następujących czynności: [31]}
- suma jest dokładnie słuszna! Znaleźliśmy odpowiedź.
- suma była za mała. Przesuń
j
bliżej końca, aby wybrać następną największą liczbę. - suma była zbyt duża. Przesuń
k
bliżej początku, aby wybrać następną najmniejszą liczbę.
Dla każdego i
, wskaźniki j
i k
będą stopniowo zbliżać się do siebie nawzajem. W końcu będą się mijać i w tym momencie nie musimy próbować niczego innego do tego i
, ponieważ będziemy sumować te same elementy, tylko w innej kolejności. Po tym punkcie spróbujemy następnego i
i powtórzymy.
W końcu albo wyczerpamy użyteczne możliwości, albo znajdziemy rozwiązanie. Widać, że to jest O (n2) ponieważ wykonujemy pętlę zewnętrzną O (N) razy i wykonujemy pętlę wewnętrzną O (N) razy. Jest to możliwe sub-kwadratycznie, jeśli masz naprawdę fantazję, reprezentując każdą liczbę całkowitą jako wektor bitowy i wykonując szybką transformatę Fouriera, ale to wykracza poza zakres tej odpowiedzi.
Uwaga: ponieważ jest to pytanie z wywiadu, trochę oszukałem: algorytm ten pozwala na wielokrotne wybieranie tego samego elementu. Oznacza to, że (-1, -1, 2) byłoby poprawnym rozwiązaniem, podobnie jak (0, 0, 0). Znajduje również tylko dokładne odpowiedzi, a nie najbliższą odpowiedź, ponieważ tytuł wspomina. Jako ćwiczenie dla czytelnika, pozwolę ci dowiedzieć się, jak sprawić, by działało tylko z odrębnymi elementami (ale to bardzo prosta zmiana) i dokładnymi odpowiedziami (które są również prostą zmianą).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-03-18 19:11:57
Z pewnością jest to lepsze rozwiązanie, ponieważ jest łatwiejsze do odczytania, a tym samym mniej podatne na błędy. Jedynym problemem jest to, że musimy dodać kilka linii kodu, aby uniknąć wielokrotnego wyboru jednego elementu.
Inne rozwiązanie O (n^2) (za pomocą hashset).
// K is the sum that we are looking for
for i 1..n
int s1 = K - A[i]
for j 1..i
int s2 = s1 - A[j]
if (set.contains(s2))
print the numbers
set.add(A[i])
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-02-24 23:55:41
Może coś takiego, czyli O (n^2)
for(each ele in the sorted array)
{
ele = arr[i] - YOUR_NUMBER;
let front be the pointer to the front of the array;
let rear be the pointer to the rear element of the array.;
// till front is not greater than rear.
while(front <= rear)
{
if(*front + *rear == ele)
{
print "Found triplet "<<*front<<","<<*rear<<","<<ele<<endl;
break;
}
else
{
// sum is > ele, so we need to decrease the sum by decrementing rear pointer.
if((*front + *rear) > ele)
decrement rear pointer.
// sum is < ele, so we need to increase the sum by incrementing the front pointer.
else
increment front pointer.
}
}
To stwierdzi, czy suma 3 elementów jest dokładnie równa Twojej liczbie. Jeśli chcesz być najbliżej, możesz zmodyfikować go tak, aby zapamiętał najmniejszą deltę (różnicę między liczbą bieżącej trójki), a na końcu wydrukować trójkę odpowiadającą najmniejszej delcie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-01-15 09:36:21
Rozwiązanie Johna Feminella ma błąd.
Na linii
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
Musimy sprawdzić,czy ja,j, k są różne. W przeciwnym razie, jeśli mój element docelowy to 6
i jeśli moja tablica wejściowa zawiera {3,2,1,7,9,0,-4,6}
. Jeśli wydrukuję krotki, które sumują się do 6, wtedy otrzymam również 0,0,6
jako wyjście . Aby tego uniknąć, musimy zmodyfikować warunek w ten sposób.
if ((A[i] + A[j] + A[k] == 0) && (i!=j) && (i!=k) && (j!=k)) return (A[i], A[j], A[k])
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-08-27 16:29:46
Zauważ, że mamy posortowaną tablicę. Rozwiązanie to jest podobne do rozwiązania Jana, tylko że szuka sumy i nie powtarza tego samego elementu.
#include <stdio.h>;
int checkForSum (int arr[], int len, int sum) { //arr is sorted
int i;
for (i = 0; i < len ; i++) {
int left = i + 1;
int right = len - 1;
while (right > left) {
printf ("values are %d %d %d\n", arr[i], arr[left], arr[right]);
if (arr[right] + arr[left] + arr[i] - sum == 0) {
printf ("final values are %d %d %d\n", arr[i], arr[left], arr[right]);
return 1;
}
if (arr[right] + arr[left] + arr[i] - sum > 0)
right--;
else
left++;
}
}
return -1;
}
int main (int argc, char **argv) {
int arr[] = {-99, -45, -6, -5, 0, 9, 12, 16, 21, 29};
int sum = 4;
printf ("check for sum %d in arr is %d\n", sum, checkForSum(arr, 10, sum));
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-05-03 07:57:07
Oto kod C++:
bool FindSumZero(int a[], int n, int& x, int& y, int& z)
{
if (n < 3)
return false;
sort(a, a+n);
for (int i = 0; i < n-2; ++i)
{
int j = i+1;
int k = n-1;
while (k >= j)
{
int s = a[i]+a[j]+a[k];
if (s == 0 && i != j && j != k && k != i)
{
x = a[i], y = a[j], z = a[k];
return true;
}
if (s > 0)
--k;
else
++j;
}
}
return false;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-09-22 09:32:40
Bardzo proste rozwiązanie N^2*logN: posortować tablicę wejściową, następnie przejść przez wszystkie pary ai, aj (N^2 Czas), i dla każdej pary sprawdzić, czy (S - ai - aj) jest w tablicy (logN time).
Inne rozwiązanie O (S*N) wykorzystuje klasyczne podejście programowanie dynamiczne.
W skrócie:
Utwórz tablicę 2-d V [4] [S + 1]. Wypełnij go w taki sposób, aby:
V[0][0] = 1, V[0][x] = 0;
V1[A i ]= 1 dla dowolnego i, V1[x] = 0 dla wszystkich pozostałych x
V [2] [A i + a j ]= 1, dla dowolnych i, j. V[2] [x] = 0 dla wszystkich pozostałych x
V [3] [suma dowolnych 3 elementów] = 1.
Aby go wypełnić, iterate przez i , dla każdego a i iterate przez tablicę od prawej do lewej.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-01-15 09:17:08
Można to skutecznie rozwiązać W O (N log (n)) w następujący sposób. Podaję rozwiązanie, które mówi, czy suma dowolnych trzech liczb jest równa danej liczbie.
import java.util.*;
public class MainClass {
public static void main(String[] args) {
int[] a = {-1, 0, 1, 2, 3, 5, -4, 6};
System.out.println(((Object) isThreeSumEqualsTarget(a, 11)).toString());
}
public static boolean isThreeSumEqualsTarget(int[] array, int targetNumber) {
//O(n log (n))
Arrays.sort(array);
System.out.println(Arrays.toString(array));
int leftIndex = 0;
int rightIndex = array.length - 1;
//O(n)
while (leftIndex + 1 < rightIndex - 1) {
//take sum of two corners
int sum = array[leftIndex] + array[rightIndex];
//find if the number matches exactly. Or get the closest match.
//here i am not storing closest matches. You can do it for yourself.
//O(log (n)) complexity
int binarySearchClosestIndex = binarySearch(leftIndex + 1, rightIndex - 1, targetNumber - sum, array);
//if exact match is found, we already got the answer
if (-1 == binarySearchClosestIndex) {
System.out.println(("combo is " + array[leftIndex] + ", " + array[rightIndex] + ", " + (targetNumber - sum)));
return true;
}
//if exact match is not found, we have to decide which pointer, left or right to move inwards
//we are here means , either we are on left end or on right end
else {
//we ended up searching towards start of array,i.e. we need a lesser sum , lets move inwards from right
//we need to have a lower sum, lets decrease right index
if (binarySearchClosestIndex == leftIndex + 1) {
rightIndex--;
} else if (binarySearchClosestIndex == rightIndex - 1) {
//we need to have a higher sum, lets decrease right index
leftIndex++;
}
}
}
return false;
}
public static int binarySearch(int start, int end, int elem, int[] array) {
int mid = 0;
while (start <= end) {
mid = (start + end) >>> 1;
if (elem < array[mid]) {
end = mid - 1;
} else if (elem > array[mid]) {
start = mid + 1;
} else {
//exact match case
//Suits more for this particular case to return -1
return -1;
}
}
return mid;
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-10-25 04:54:30
Redukcja: myślę, że @ John Feminella rozwiązanie o (n2) jest najbardziej eleganckie. Możemy jeszcze zmniejszyć A [n] w którym szukać krotki. Obserwując [k] tak, że wszystkie elementy byłyby w [0]-a [k], gdy nasza tablica wyszukiwania jest ogromna, a suma (S) naprawdę mała.
A[0] jest minimum: - rosnąco sortowana tablica.
S = 2A[0] + A[k]: podane s I A [] możemy znaleźć[k] za pomocą wyszukiwania binarnego w czasie log(n).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-10-14 13:40:34
Inne rozwiązanie, które sprawdza i nie sprawdza się wcześniej:
public boolean solution(int[] input) {
int length = input.length;
if (length < 3) {
return false;
}
// x + y + z = 0 => -z = x + y
final Set<Integer> z = new HashSet<>(length);
int zeroCounter = 0, sum; // if they're more than 3 zeros we're done
for (int element : input) {
if (element < 0) {
z.add(element);
}
if (element == 0) {
++zeroCounter;
if (zeroCounter >= 3) {
return true;
}
}
}
if (z.isEmpty() || z.size() == length || (z.size() + zeroCounter == length)) {
return false;
} else {
for (int x = 0; x < length; ++x) {
for (int y = x + 1; y < length; ++y) {
sum = input[x] + input[y]; // will use it as inverse addition
if (sum < 0) {
continue;
}
if (z.contains(sum * -1)) {
return true;
}
}
}
}
return false;
}
Dodałem tu kilka testów jednostkowych: GivenArrayReturnTrueIfThreeElementssumzerotest .
Jeśli zestaw zajmuje zbyt dużo miejsca, mogę łatwo użyć Javy.util.BitSet, który będzie używał O (n/w) spacji .
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-08-11 14:55:06
Oto program w Javie O (N^2)
import java.util.Stack;
public class GetTripletPair {
/** Set a value for target sum */
public static final int TARGET_SUM = 32;
private Stack<Integer> stack = new Stack<Integer>();
/** Store the sum of current elements stored in stack */
private int sumInStack = 0;
private int count =0 ;
public void populateSubset(int[] data, int fromIndex, int endIndex) {
/*
* Check if sum of elements stored in Stack is equal to the expected
* target sum.
*
* If so, call print method to print the candidate satisfied result.
*/
if (sumInStack == TARGET_SUM) {
print(stack);
}
for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
if (sumInStack + data[currentIndex] <= TARGET_SUM) {
++count;
stack.push(data[currentIndex]);
sumInStack += data[currentIndex];
/*
* Make the currentIndex +1, and then use recursion to proceed
* further.
*/
populateSubset(data, currentIndex + 1, endIndex);
--count;
sumInStack -= (Integer) stack.pop();
}else{
return;
}
}
}
/**
* Print satisfied result. i.e. 15 = 4+6+5
*/
private void print(Stack<Integer> stack) {
StringBuilder sb = new StringBuilder();
sb.append(TARGET_SUM).append(" = ");
for (Integer i : stack) {
sb.append(i).append("+");
}
System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
}
private static final int[] DATA = {4,13,14,15,17};
public static void main(String[] args) {
GetAllSubsetByStack get = new GetAllSubsetByStack();
get.populateSubset(DATA, 0, DATA.length);
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-08-06 12:36:17
Problem można rozwiązać W O (N^2) poprzez rozszerzenie problemu 2-sumowego o drobne modyfikacje.A jest wektorem zawierającym elementy, A B jest wymaganą sumą.
Int Solution:: threeSumClosest (vector &a, int B) {
sort(A.begin(),A.end());
int k=0,i,j,closest,val;int diff=INT_MAX;
while(k<A.size()-2)
{
i=k+1;
j=A.size()-1;
while(i<j)
{
val=A[i]+A[j]+A[k];
if(val==B) return B;
if(abs(B-val)<diff)
{
diff=abs(B-val);
closest=val;
}
if(B>val)
++i;
if(B<val)
--j;
}
++k;
}
return closest;
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-07-12 23:26:24
Zrobiłem to w n^3, Mój pseudokod jest poniżej;
//Utwórz hashmapę z kluczem jako liczbą całkowitą i wartością jako ArrayList //iterate przez list używając pętli for, dla każdej wartości w liście iterate ponownie zaczynając od następnej wartości;
for (int i=0; i<=arr.length-1 ; i++){
for (int j=i+1; j<=arr.length-1;j++){
//jeśli suma arr[i] i arr [j] jest mniejsza od wymaganej sumy, to istnieje możliwość znalezienia trzeciej cyfry, więc zrób inną dla pętli
if (arr[i]+arr[j] < sum){
for (int k= j+1; k<=arr.length-1;k++)
/ / w tym przypadku szukamy teraz trzeciej wartości; jeśli suma arr [i] i arr [j] oraz arr[k] to żądana suma następnie dodaj je do Hashmapy, czyniąc arr [i] kluczem, a następnie dodając arr [j] i arr [k] do ArrayList w wartości tego klucza
if (arr[i]+arr[j]+arr[k] == sum){
map.put(arr[i],new ArrayList<Integer>());
map.get(arr[i]).add(arr[j]);
map.get(arr[i]).add(arr[k]);}
Po tym masz teraz słownik, który zawiera wszystkie wpisy reprezentujące trzy wartości dodawane do żądanej sumy. Wyodrębnij wszystkie te wpisy za pomocą funkcji HashMap. Zadziałało idealnie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-11-18 22:49:50