Dwie sumy - projektowanie algorytmu optymalizacji wstępnego sortowania

Question

🧩 Czy można zoptymalizować czas działania rozwiązania z dwiema sumami, otrzymując wstępnie posortowane dane wejściowe w kolejności rosnącej lub malejącej?

🚀 Oryginalne dwie sumy

Określ, czy istnieją dwa elementy, których indywidualna pojemność będzie idealnie równa całkowitej pojemności, zapewniając jednocześnie, że ten sam element nie może być wybrany dwukrotnie.

• Dane wejściowe: Int reprezentujący całkowitą pojemność i tablicę Int reprezentujących indywidualne zdolności elementów.
• Dane wyjściowe: wartość logiczna określająca, czy dwie pozycje mogą równać się całkowitej wydajności.
• Złożoność czasowa: wzrost liniowy, $O(n)$
• Złożoność przestrzeni: wzrost liniowy, $O(n)$

Próbki

Wejście: [4, 5, 2, 6]

• Całkowita pojemność: 10
• Oczekiwać: true

Wejście: [4, 5, 2, 5]

• Całkowita pojemność: 10
• Oczekiwać: true

Wejście: [4, 5, 2, 7]

• Całkowita pojemność: 10
• Oczekiwać: false

Pseudo kod

1. Utwórz zestaw, searchSetaby przechowywać elementy, które zostały już zbadane.

2. Iteruj przez wejściową tablicę pojemności przedmiotów.

   2a. Znajdź targetCapacitydla bieżącej pozycji:totalCapacity - itemCapacity

   2b. Jeśli searchSetzawiera targetCapacity, return true.

   2c. W przeciwnym razie dodaj itemCapacitydo searchSet.

3. Zwróć, falsejeśli całe wejście jest iterowane bez znalezienia dopasowania.

🏗️ Sortowanie wstępne

1. Zapisz nową zmienną lastTargetCapacity
2. Jeśli bieżąca itemCapacity< lastTargetCapacity, nie ma możliwych dwóch sum i powrotu false.

to znaczy

Wejście: [6,2,1,0]

• Całkowita pojemność: 9

Iteracje

1. targetCapacity = 9 - 6, lastTargetCapacity= 3
2. Zwróć false, ponieważ itemCapacityof 2< lastTargetCapacityof 3.

Answer 1

Rozwiązanie Two Sum można zoptymalizować pod kątem wydajności w czasie wykonywania, biorąc pod uwagę, że tablica wejściowa jest wstępnie posortowana w kolejności rosnącej lub malejącej.

Jeśli wyszukiwanie binarne jest używane do znalezienia targetCapacitypowyższego, będzie działać logarytmicznie,$O(logn)$, średni czas pracy. Jest to szybsze niż powyższy pseudokod, który działa liniowo,$O(n)$, środowisko wykonawcze przy użyciu iteracji i mieszania.

Gdyby dane wejściowe nie zawierały sortowania, nie byłoby możliwe sortowanie i wyszukiwanie szybciej niż $O(n)$. Najlepsze, co można zrobić, byłoby$O(nlogn)$ ze strategiami takimi jak Quicksort i Binary Search.

Zobacz: Stanford - Wyjaśnienie dwóch sum

Answer 2

Tak, możesz rozwiązać problem dwóch sum w formacie $O(n)$czas, jeśli liczby są przedstawione w kolejności posortowanej. Zobacz moją drugą odpowiedź, jak to zrobić; obejmuje skanowanie liniowe. Jest to asymptotycznie optymalne, tak jak to już trwa$O(n)$ czas nawet na odczytanie danych wejściowych, a rozwiązanie problemu może wymagać przeczytania całego wejścia, więc nie ma dalszej asymptotycznej poprawy.