Leetcode: Produkt des Arrays außer sich selbst

Dieses Problem scheint in linearer Zeit und Raum einfach zu lösen. Dieses Problem baut auf einigen grundlegenden Konzepten von Arrays auf.

1. Array-Durchquerungen.
2. Präfix- und Suffixsumme.

Unternehmen, die dies in ihrem Coding-Interview gefragt haben, sind Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe und viele weitere Top-Tech-Unternehmen.

Problemstellung

Geben Sie bei einem gegebenen ganzzahligen Array nums eine Array-Antwort zurück, sodass Antwort[i] gleich dem Produkt aller Elemente von nums außer nums[i] ist.

Das Produkt eines beliebigen Präfixes oder Suffixes von Zahlen passt garantiert in eine 32-Bit Ganzzahl.

Sie müssen einen Algorithmus schreiben, der in O(n)-Zeit und ohne Verwendung der Divisionsoperation ausgeführt wird.

Testfall Nr. 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Testfall Nr. 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Das Problem verstehen

Dieses Problem scheint in linearer Zeit und Raum einfacher zu lösen, ist jedoch beim Schreiben des Pseudocodes oder der tatsächlichen Codeimplementierung schwierig.

Illustration

Lassen Sie uns sehen, welche Ergebnisse von einem einfachen Array mit 4 Elementen erwartet werden:

input = {1, 2, 3, 4}

Der Wert an jedem Index ist also das Produkt aller anderen Elemente im Array außer dem Wert selbst. Die folgende Abbildung veranschaulicht dies.

Basierend auf der obigen Abbildung können wir eine Formel aufstellen. Für jeden gegebenen Index i können wir den Wert ermitteln, indem wir das Produkt der Elemente von o bis (i – 1) plus das Produkt der Elemente von (i + 1) bis (N – 1) verwenden. Dies wird in der folgenden Abbildung veranschaulicht:

Denkprozess

Bevor Sie Pseudocode schreiben, überlegen Sie sich Fragen und stellen Sie diese dem Interviewer.

1. Muss ich mir wegen Duplikaten Sorgen machen?
2. Was ist, wenn das Array leer ist oder ein einzelnes Element enthält? Was sind die erwarteten Ergebnisse?
3. Sollte ich den Wert 0 in einem der Indizes im Array berücksichtigen/ignorieren? weil alle anderen Werte 0 erhalten, außer dem Index, der 0 enthält.
4. Was sind die Eck-/Randfälle für dieses Problem?

Sobald Sie und der Interviewer die oben genannten Fragen besprochen haben, überlegen Sie sich verschiedene Lösungsansätze für das Problem.

1. Naiver Ansatz/brutale Gewalt.
2. Produkt aller Elemente.
3. Linke und rechte Produkte.
4. Präfix- und Suffixsummen.

Ansatz 1: Naiv/Brute-Force

Intuition

Um den Brute-Force-Ansatz anzuwenden, müssen wir zwei for-Schleifen ausführen. Wenn der Index der äußeren Schleife mit dem Indexwert der inneren Schleife übereinstimmt, sollten wir das Produkt überspringen. andernfalls fahren wir mit dem Produkt fort.

Algorithmus

1. Variablen initialisieren:
   • N = nums.length (Länge des Eingabearrays).
   • result = new int[N] (Array zum Speichern der Ergebnisse).
2. Äußere Schleife (Durchlaufen Sie jedes Element in Zahlen):
   • Für i = 0 bis N-1: CurrentProduct = 1 initialisieren.
3. Innere Schleife (Produkt für aktuelles Element berechnen), für j = 0 bis N-1:
   • Wenn i == j, überspringen Sie die aktuelle Iteration mit „Weiter“.
   • AktuellesProdukt mit nums[j] multiplizieren.
   • Aktuelles Produkt dem Ergebnis[i] zuweisen.
4. Ergebnis zurückgeben.

Code

// brute force
static int[] bruteForce(int[] nums) {
    int N = nums.length;
    int[] result = new int[N];

    for (int i = 0; i < N; i++) {
        int currentProduct = 1;
        for (int j = 0; j < N; j++) {
            if (i == j) {
                continue;
            }
            currentProduct *= nums[j];
        }
        result[i] = currentProduct;
    }
    return result;
}

Komplexitätsanalyse

1. Zeitkomplexität: O(n^2), zum zweimaligen Durchlaufen des Arrays in äußeren und inneren Schleifen.
2. Raumkomplexität: O(n), für den Hilfsraum (Ergebnis[]-Array), den wir verwendet haben.

Ansatz 2: Produkt des Arrays ❌

Eine Möglichkeit, die die meisten Entwickler denken, besteht darin, eine Produktsumme aller Elemente auszuführen, die Produktsumme durch jeden Array-Wert zu dividieren und das Ergebnis zurückzugeben.

Pseudocode

// O(n) time and O(1) space
p = 1
for i -> 0 to A[i]
  p * = A[i]
for i -> 0 to (N - 1)
  A[i] = p/A[i] // if A[i] == 0 ? BAM error‼️  

Code

// code implementation
static int[] productSum(int[] nums) {
    int product_sum = 1;
    for(int num: nums) {
        product_sum *= num;
    }

    for(int i = 0; i < nums.length; i++) {
        nums[i] = product_sum/nums[i];
    }
    return nums;
}

Was passiert, wenn eines der Array-Elemente 0 enthält? ?

Der Wert aller Indizes außer dem Index, der 0 enthält, ist definitiv unendlich. Außerdem löst der Code java.lang.ArithmeticException.
aus

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at dev.ggorantala.ds.arrays.ProductOfArrayItself.productSum(ProductOfArrayItself.java:24)
    at dev.ggorantala.ds.arrays.ProductOfArrayItself.main(ProductOfArrayItself.java:14)

Ansatz 3: Präfix- und Suffixprodukt finden

Erfahren Sie mehr über die Präfix- und Suffixsumme im Arrays Mastery-Kurs auf meiner Website https://ggorantala.dev

Intuition und Formeln

Präfix und Suffix werden berechnet, bevor ein Algorithmus für das Ergebnis geschrieben wird. Die Summenformeln für Präfixe und Suffixe sind unten aufgeführt:

Algorithm Steps

1. Create an array result of the same length as nums to store the final results.
2. Create two additional arrays prefix_sum and suffix_sum of the same length as nums.
3. Calculate Prefix Products:
   • Set the first element of prefix_sum to the first element of nums.
   • Iterate through the input array nums starting from the second element (index 1). For each index i, set prefix_sum[i] to the product of prefix_sum[i-1] and nums[i].
4. Calculate Suffix Products:
   • Set the last element of suffix_sum to the last element of nums.
   • Iterate through the input array nums starting from the second-to-last element (index nums.length - 2) to the first element. For each index i, set suffix_sum[i] to the product of suffix_sum[i+1] and nums[i].
5. Calculate the result: Iterate through the input array nums.
   • For the first element (i == 0), set result[i] to suffix_sum[i + 1].
   • For the last element (i == nums.length - 1), set result[i] to prefix_sum[i - 1].
   • For all other elements, set result[i] to the product of prefix_sum[i - 1] and suffix_sum[i + 1].
6. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

Function usingPrefixSuffix(nums):
    N = length of nums
    result = new array of length N
    prefix_sum = new array of length N
    suffix_sum = new array of length N

    // Calculate prefix products
    prefix_sum[0] = nums[0]
    For i from 1 to N-1:
        prefix_sum[i] = prefix_sum[i-1] * nums[i]

    // Calculate suffix products
    suffix_sum[N-1] = nums[N-1]
    For i from N-2 to 0:
        suffix_sum[i] = suffix_sum[i+1] * nums[i]

    // Calculate result array
    For i from 0 to N-1:
        If i == 0:
            result[i] = suffix_sum[i+1]
        Else If i == N-1:
            result[i] = prefix_sum[i-1]
        Else:
            result[i] = prefix_sum[i-1] * suffix_sum[i+1]

    Return result

Code

// using prefix and suffix arrays
private static int[] usingPrefixSuffix(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];
    int[] suffix_sum = new int[nums.length];

    // prefix sum calculation
    prefix_sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i];
    }

    // suffix sum calculation
    suffix_sum[nums.length - 1] = nums[nums.length - 1];
    for (int i = nums.length - 2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        if (i == 0) { // when variable `i` is at 0th index
            result[i] = suffix_sum[i + 1];
        } else if (i == nums.length - 1) { // when variable `i` is at last index 
            result[i] = prefix_sum[i - 1];
        } else { // for all other indexes
            result[i] = prefix_sum[i - 1] * suffix_sum[i + 1];
        }
    }
    return result;
}

Complexity analysis

1. Time complexity: The time complexity of the given code is O(n), where n is the length of the input array nums. This is because:
   • Calculating the prefix_sum products take O(n) time.
   • Calculating the suffix_sum products take O(n) time.
   • Constructing the result array takes O(n) time.

Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).

1. Space complexity: The space complexity of the given code is O(n). This is because:
   • The prefix_sum array requires O(n) space.
   • The suffix_sum array requires O(n) space.
   • Theresult array requires O(n) space. All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).

Optimization ?

For the suffix array calculation, we override the input nums array instead of creating one.

private static int[] usingPrefixSuffixOptimization(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];

    // prefix sum calculation
    prefix_sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i];
    }

    // suffix sum calculation, in-place - `nums` array override
    for (int i = nums.length - 2; i >= 0; i--) {
        nums[i] = nums[i + 1] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        if (i == 0) { // when variable `i` is at 0th index
            result[i] = nums[i + 1];
        } else if (i == nums.length - 1) { // when variable `i` is at last index
            result[i] = prefix_sum[i - 1];
        } else { // for all other indexes
            result[i] = prefix_sum[i - 1] * nums[i + 1];
        }
    }
    return result;
}

Hence, we reduced the space of O(n). Time and space are not reduced, but we did a small optimization here.

Approach 4: Using Prefix and Suffix product knowledge ?

Intuition

This is a rather easy approach when we use the knowledge of prefix and suffix arrays.

For every given index i, we will calculate the product of all the numbers to the left and then multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index i. Let's look at a formal algorithm that describes this idea more clearly.

Algorithm steps

1. Create an array result of the same length as nums to store the final results.
2. Create two additional arrays prefix_sum and suffix_sum of the same length as nums.
3. Calculate Prefix Products:
   • Set the first element of prefix_sum to 1.
   • Iterate through the input array nums starting from the second element (index 1). For each index i, set prefix_sum[i] to the product of prefix_sum[i - 1] and nums[i - 1].
4. Calculate Suffix Products:
   • Set the last element of suffix_sum to 1.
   • Iterate through the input array nums starting from the second-to-last element (index nums.length - 2) to the first element.
   • For each index i, set suffix_sum[i] to the product of suffix_sum[i + 1] and nums[i + 1].
5. Iterate through the input array nums.
   • For each index i, set result[i] to the product of prefix_sum[i] and suffix_sum[i].
6. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

Function prefixSuffix1(nums):
    N = length of nums
    result = new array of length N
    prefix_sum = new array of length N
    suffix_sum = new array of length N

    // Calculate prefix products
    prefix_sum[0] = 1
    For i from 1 to N-1:
        prefix_sum[i] = prefix_sum[i-1] * nums[i-1]

    // Calculate suffix products
    suffix_sum[N-1] = 1
    For i from N-2 to 0:
        suffix_sum[i] = suffix_sum[i+1] * nums[i+1]

    // Calculate result array
    For i from 0 to N-1:
        result[i] = prefix_sum[i] * suffix_sum[i]

    Return result

Code

private static int[] prefixSuffixProducts(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];
    int[] suffix_sum = new int[nums.length];

    prefix_sum[0] = 1;
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i - 1];
    }

    suffix_sum[nums.length - 1] = 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] * nums[i + 1];
    }

    for (int i = 0; i < nums.length; i++) {
        result[i] = prefix_sum[i] * suffix_sum[i];
    }

    return result;
}

Complexity analysis

1. Time complexity: The time complexity of the given code is O(n), where n is the length of the input array nums. This is because:
   • Calculating the prefix_sum products take O(n) time.
   • Calculating the suffix_sum products take O(n) time.
   • Constructing the result array takes O(n) time.

Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).

1. Space complexity: The space complexity of the given code is O(n). This is because:
   • The prefix_sum array requires O(n) space.
   • The suffix_sum array requires O(n) space.
   • The result array requires O(n) space.

All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).

Approach 5: Carry Forward technique

Intuition

The carry forward technique optimizes us to solve the problem with a more efficient space complexity. Instead of using two separate arrays for prefix and suffix products, we can use the result array itself to store intermediate results and use a single pass for each direction.

Here’s how you can implement the solution using the carry-forward technique:

Algorithm Steps for Carry Forward Technique

1. Initialize Result Array:
   • Create an array result of the same length as nums to store the final results.
2. Calculate Prefix Products:
   • Initialize a variable prefixProduct to 1.
   • Iterate through the input array nums from left to right. For each index i, set result[i] to the value of prefixProduct. Update prefixProduct by multiplying it with nums[i].
3. Calculate Suffix Products and Final Result:
   • Initialize a variable suffixProduct to 1.
   • Iterate through the input array nums from right to left. For each index i, update result[i] by multiplying it with suffixProduct. Update suffixProduct by multiplying it with nums[i].
4. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

prefix products
    prefixProduct = 1
    For i from 0 to N-1:
        result[i] = prefixProduct
        prefixProduct = prefixProduct * nums[i]

    // Calculate suffix products and finalize result
    suffixProduct = 1
    For i from N-1 to 0:
        result[i] = result[i] * suffixProduct
        suffixProduct = suffixProduct * nums[i]

    Return result

Code

// carry forward technique
private static int[] carryForward(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

    // Calculate prefix products
    int prefixProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = prefixProduct;
        prefixProduct *= nums[i];
    }

    // Calculate suffix products and finalize the result
    int suffixProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }
    return result;
}

Explanation

1. Prefix Products Calculation:
   • We initialize prefixProduct to 1 and update each element of result with the current value of prefixProduct.
   • Update prefixProduct by multiplying it with nums[i].
2. Suffix Products Calculation:
   • We initialize suffixProduct to 1 and update each element of result(which already contains the prefix product) by multiplying it with suffixProduct.
   • Update suffixProduct by multiplying it with nums[i].

Complexity analysis

1. Time Complexity: O(n) time
2. Space Complexity: O(n) (for the result array)

This approach uses only a single extra array (result) and two variables (prefixProduct and suffixProduct), achieving efficient space utilization while maintaining O(n) time complexity.

Das obige ist der detaillierte Inhalt vonLeetcode: Produkt des Arrays außer sich selbst. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!