Znajdź wszystkie triplety w tablicy z sumą mniejszą lub równą podanej sumie.

Question

To zostało niedawno zadane znajomemu w wywiadzie i nie znamy żadnego innego rozwiązania poza prostym O (n).

Czy istnieje jakiś lepszy algorytm?

Chodzi o to, aby znaleźć wszystkie tryplety w tablicy całkowitej, których suma jest mniejsza niż lub równa określonej sumy S

uwaga: nie widać innych takich problemów na tak z wydajnością O (N log n), ale wszystkie z nich rozwiązały łatwiejszą wersję tego problemu, np. gdzie arr[i] + arr[j] + arr[k] = S lub gdzie tylko sprawdzały, czy istnieje jeden taki triplet.

Moje pytanie jest, aby znaleźć wszystkie i,j,k w arr[] takie, że arr[i] + arr[j] + arr[k] <= S

Answer 1

Od najgorszym asymptotycznej punktu widzenia, nie ma lepszego algorytm ponieważ wielkość produkcji jest potencjalnie O(n^3).

np. Niech tablica będzie liczbą od 1 do n. Niech S = 3n. Oczywiście każdy podzbiór trzech elementów tablicy będzie mniejszy niż S i istnieją podzbiory (n choose 3) = O(n^3).

Istnieje kilka sposobów na przyspieszenie najgorszych przypadków. Na przykład spróbuj najpierw sortować tablicę. To powinno dać ci wskazówki.

Answer 2

Mam pomysł, ale nie jestem pewien, czy to działa.

Preprocess (usuń elementy>S) i najpierw sortuj tablicę.

Następnie, po zbierając arr[i] i arr[j] gdzie i < j, możesz wyszukiwania binarnego S - arr[i] - arr[j] w pozostałej array[j+1...n]. Po przeszukaniu binarnym indeksu m, może leżeć między j+1 i m.

Myślę, że może to zmniejszyć złożoność. Co myślisz?

Answer 3

Jaka byłaby złożoność tego?

Po zastosowaniu do posortowanej listy (rosnąco), f po prostu wyświetla trójki, których suma jest mniejsza lub równa s, jedna po drugiej, bez tworzenia duplikatów lub skanowania za pierwszym elementem, który jest zbyt duży.

kod Haskell:

f []  s result = if length result == 3 then [result] else [] 
f (x:xs) s result 
    | length result == 3 = [result] 
    | x + sum result > s = [] 
    | otherwise   = f xs s (x:result) ++ f xs s result 

wyjściowa:

*Main> length $ f [1..300] 300 [] 
731375 
(5.09 secs, 402637784 bytes) 

*Main> f [1..10] 13 [] 
[[3,2,1],[4,2,1],[5,2,1],[6,2,1],[7,2,1],[8,2,1],[9,2,1],[10,2,1],[4,3,1] 
,[5,3,1],[6,3,1],[7,3,1],[8,3,1],[9,3,1],[5,4,1],[6,4,1],[7,4,1],[8,4,1] 
,[6,5,1],[7,5,1],[4,3,2],[5,3,2],[6,3,2],[7,3,2],[8,3,2],[5,4,2],[6,4,2] 
,[7,4,2],[6,5,2],[5,4,3],[6,4,3]] 

Answer 4

ten może być rozwiązany w O (N^2) złożoności.

sortowanie numery -> O (nlog (n))

Zaczynając od przodu rozwiązać jeden numer w czasie. Teraz problem zmniejsza się, aby znaleźć 2 liczby w posortowanej tablicy, której suma wynosi < = podana suma.Używając 2 wskaźników, jednego od początku i jednego od końca, można to rozwiązać w O (n). Więc ogólna złożoność jest O (n2)

Answer 5

Wierzę, że ten algorytm powinien załatwić sprawę w O (N^2). Najpierw jednak należy posortować tablicę.

Zasadniczo znajduję wszystkie możliwe tryplety, w których pierwszy indeks i wynosi zero, a następny indeks to j przeszukując pozostałe indeksy (k) dla wszystkich sum mniejszych niż lub równych x (lub S w twoim przypadku). Następnie zwiększam j o 1 i powtarzam proces. Kiedy j dojdzie do końca tablicy, rozpoczynam proces od tego, że jestem teraz i + 1 i kontynuuję pracę do momentu, w którym osiągną wartość od drugiej do ostatniej wartości indeksu (ponieważ w tym momencie nie ma już możliwych trioli).

kod Python

def numTriplets(a,x): 
    if len(a) < 3: 
     return None 
    i = 0 
    j = 1 
    triplets = [] 
    while True: 
     for k in range(j+1,len(a)): 
     if a[i] + a[j] + a[k] <= x: 
      triplets.append([i,j,k]) 
     j += 1 
     if j == len(a) - 1: 
     i += 1 
     j = i + 1 
     if i == len(a) - 2: 
     return triplets