Product of Array Except Self

Q: Dlaczego dzielenie jest niedozwolone w zadaniu „Iloczyn tablicy bez bieżącego elementu”?

Dzielenie całkowitego iloczynu przez nums[i] nie działa, gdy tablica zawiera zero, ponieważ całkowity iloczyn wynosi 0, a dla indeksu tego zera trzeba byłoby dzielić przez 0. Aby to zadziałało, trzeba zliczyć zera i uwzględnić szczególne przypadki. Ta zasada skłania do użycia iloczynów prefiksowych i sufiksowych, które obsługują zera bez żadnych szczególnych przypadków.

ŚrednieSumy prefiksowe

+10

Otrzymujesz tablicę liczb całkowitych nums. Zwróć tablicę answer o tej samej długości, w której answer[i] jest iloczynem wszystkich elementów nums z wyjątkiem elementu o indeksie i. Wykonaj to w czasie O(n) i bez używania dzielenia.

Funkcja

productExceptSelf(nums: integer-array) → integer-array

numsinteger-array: tablica liczb całkowitych zawierająca co najmniej dwa elementy
Zwracainteger-array: tablica, której wartością pod indeksem i jest iloczyn wszystkich elementów z wyjątkiem nums[i]

Ograniczenia

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
Iloczyn wszystkich niezerowych wartości w nums mieści się w 32-bitowej liczbie całkowitej ze znakiem, więc każdy iloczyn obliczany po drodze również się mieści.

Przykłady

Wejście: nums = [2, 3, 4, 5]
Wyjście: [60, 40, 30, 24]
Wyjaśnienie: Pominięcie 2 daje 3 × 4 × 5 = 60, a pominięcie 5 daje 2 × 3 × 4 = 24. Dwa środkowe działają tak samo: 2 × 4 × 5 = 40 i 2 × 3 × 5 = 30.

Pytanie dodatkowe

Czy możesz użyć tylko O(1) dodatkowej pamięci, nie licząc zwracanej tablicy?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Iloczyn wszystkich wartości poza nums[i] to iloczyn wartości po jego lewej stronie pomnożony przez iloczyn wartości po jego prawej stronie. Dzielenie całkowitego iloczynu przez nums[i] wygląda na krótsze rozwiązanie, ale tutaj nie jest dozwolone i nie działa dla zer, gdyż wtedy całkowity iloczyn wynosi 0. Iloczyny prefiksowe i sufiksowe pozwalają obliczyć każdy iloczyn z lewej i prawej strony w dwóch przebiegach, więc rozwiązanie działa w czasie O(n). Tablica wynikowa może przechowywać iloczyny z lewej strony, a jedna zmienna może przechowywać iloczyn z prawej strony, więc nie jest potrzebna żadna inna tablica.

Pomnóż pozostałe wartości dla każdego indeksu

Poprawne, ale nie kończy się na największych testach

Intuicja

Postępuj zgodnie z definicją. Dla każdego indeksu i rozpocznij od iloczynu równego 1 i pomnóż przez każdą wartość nums[j], której indeks j jest różny od i. Pominięcie tego indeksu, zamiast późniejszego dzielenia przez jego wartość, sprawia, że zera nie powodują problemów: w [-2, 5, 0, 3] iloczyn dla indeksu 2 nie uwzględnia 0 i wynosi -30.

To poprawne rozwiązanie, ale powtarza obliczenia. Iloczyny dla indeksów 0 i 1 mają wspólne wszystkie wartości oprócz dwóch, a mimo to i tak mnożysz je wszystkie ponownie. Obliczenie każdej z n pozycji wymaga n-1 mnożeń, czyli łącznie około 10^8, gdy n = 10^4. C radzi sobie z tym w ułamku sekundy, ale Python, Ruby lub R potrzebują zdecydowanie za dużo czasu.

Algorytm

Utwórz tablicę wynikową o długości n.
Dla każdego indeksu i ustaw product na 1.
Pomnóż product przez każde nums[j], którego indeks j nie jest równy i.
Zapisz product pod indeksem i w tablicy wynikowej.
Zwróć wynik.

def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

Tablice iloczynów prefiksów i sufiksów

Intuicja

Podziel iloczyn dla indeksu i na dwie części: wartości przed i i wartości po nim. Nazwij te iloczyny before[i] i after[i]. Wtedy answer[i] = before[i] × after[i], a nums[i] jest pomijane bez użycia dzielenia.

Każda tablica powstaje na podstawie sąsiedniej przez jedno mnożenie. before[0] wynosi 1 — to iloczyn żadnych wartości — a before[i] = before[i-1] × nums[i-1]. Od drugiego końca after[n-1] wynosi 1, a after[i] = after[i+1] × nums[i+1]. Dla [2, 3, 4, 5] otrzymujesz before = [1, 2, 6, 24] i after = [60, 20, 5, 1], a mnożenie ich element po elemencie daje [60, 40, 30, 24].

Trzy przebiegi po n kroków dają złożoność czasową O(n). Dwie tablice pomocnicze wymagają dodatkowej pamięci O(n), którą eliminuje następne podejście.

Algorytm

Wypełnij before od lewej: before[0] = 1, a następnie każda kolejna wartość jest iloczynem poprzedniej wartości i poprzedniego elementu.
Wypełnij after od prawej: after[n-1] = 1, a następnie każda kolejna wartość jest iloczynem następnej wartości i następnego elementu.
Dla każdego indeksu ustaw answer[i] na before[i] × after[i].
Zwróć answer.

def productExceptSelf(nums):
    n = len(nums)
    # before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
    before = [1] * n
    after = [1] * n
    for i in range(1, n):
        before[i] = before[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1] * nums[i + 1]
    return [before[i] * after[i] for i in range(n)]

Iloczyn po lewej stronie w odpowiedzi, jeden iloczyn po prawej stronie

Intuicja

Nigdy nie potrzebujesz całej tablicy after naraz. Idąc od prawego końca, iloczyn wartości na prawo od i jest jedną liczbą. Przechowuj ją w zmiennej right i aktualizuj, wykonując jedno mnożenie na krok.

Zapisuj więc iloczyny po lewej stronie bezpośrednio w tablicy wynikowej w pierwszym przebiegu. W drugim przebiegu, od prawej strony, pomnóż answer[i] przez right, a dopiero potem pomnóż right przez nums[i]. Kolejność ma znaczenie: gdy używasz right dla indeksu i, nie może on jeszcze uwzględniać nums[i].

Dla [2, 3, 4, 5] po pierwszym przebiegu otrzymujemy [1, 2, 6, 24]. W drugim przebiegu używamy wartości right = 1, 5, 20, 60 dla indeksów 3, 2, 1, 0 i zamieniamy tablicę na [60, 40, 30, 24]. Czas działania nadal wynosi O(n), a poza zwracaną tablicą dodatkowa pamięć to jedna zmienna: O(1).

Algorytm

Ustaw answer[0] = 1, a następnie od lewej do prawej ustaw answer[i] = answer[i-1] × nums[i-1].
Ustaw right na 1.
Od ostatniego indeksu do 0 pomnóż answer[i] przez right.
Następnie pomnóż right przez nums[i].
Zwróć answer.

def productExceptSelf(nums):
    n = len(nums)
    # Pass 1: answer[i] = product of everything left of i
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    # Pass 2: multiply in the product of everything right of i
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

Pułapki i przypadki brzegowe

Błędy wynikają z zer, kolejności dwóch aktualizacji w drugim przebiegu oraz krawędzi tablicy.

Dzielenie całkowitego iloczynu przez nums[i] przestaje działać, gdy pojawi się 0. Dla [-2, 5, 0, 3] całkowity iloczyn wynosi 0, a dla indeksu 2 trzeba by obliczyć 0 podzielone przez 0. Można to obejść, zliczając zera, ale zasady zadania i tak wykluczają dzielenie.
Pomnożenie right przez nums[i] przed użyciem go powoduje, że nums[i] wchodzi w skład własnego iloczynu. Dla [2, 3, 4, 5] ostatnia wartość wynosi 120 zamiast 24.
Rozpoczęcie obliczania iloczynów z lewej strony od nums[0] zamiast od 1. Na lewo od indeksu 0 nic nie ma, więc iloczyn pusty wynosi 1, a answer[0] staje się iloczynem wyłącznie wartości po jego prawej stronie.
Granice pętli: przebieg od lewej odczytuje nums[i-1], więc zaczyna się od indeksu 1. Tablica sufiksów odczytuje nums[i+1], więc zaczyna się od indeksu n-2.
Dwa zera sprawiają, że każda odpowiedź wynosi 0. Jedno zero sprawia, że każda odpowiedź wynosi 0, z wyjątkiem tej pod indeksem samego zera. Przetestuj oba przypadki, zanim zaufasz swojemu kodowi.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu „iloczyn elementów tablicy z pominięciem bieżącego elementu”?

Rozwiązanie z prefiksami i sufiksami działa w czasie O(n): wymaga jednego przejścia od lewej strony i jednego od prawej. Gdy iloczyny z lewej strony są przechowywane w tablicy wynikowej, a iloczyn z prawej strony jest obliczany na bieżąco, rozwiązanie wymaga O(1) dodatkowej pamięci oprócz pamięci na wynik. Mnożenie wszystkich pozostałych wartości dla każdego indeksu zajmuje O(n²) czasu.

Dlaczego dzielenie jest niedozwolone w zadaniu „Iloczyn tablicy bez bieżącego elementu”?

Dzielenie całkowitego iloczynu przez nums[i] nie działa, gdy tablica zawiera zero, ponieważ całkowity iloczyn wynosi 0, a dla indeksu tego zera trzeba byłoby dzielić przez 0. Aby to zadziałało, trzeba zliczyć zera i uwzględnić szczególne przypadki. Ta zasada skłania do użycia iloczynów prefiksowych i sufiksowych, które obsługują zera bez żadnych szczególnych przypadków.

Czy tablica wynikowa jest uznawana za dodatkową przestrzeń?

Nie. I tak musisz zwrócić wynik, dlatego zgodnie ze zwyczajową konwencją nie uwzględnia się go w obliczaniu zużycia pamięci. Przechowywanie w nim iloczynów po lewej stronie i trzymanie iloczynu po prawej stronie w jednej zmiennej oznacza zatem dodatkowe zużycie pamięci O(1).

def productExceptSelf(nums):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

nums = [2, 3, 4, 5]

Oczekiwany wynik

[60, 40, 30, 24]

Product of Array Except Self

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Pomnóż pozostałe wartości dla każdego indeksu

Tablice iloczynów prefiksów i sufiksów

Iloczyn po lewej stronie w odpowiedzi, jeden iloczyn po prawej stronie

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania