Leetcode : Produk Tatasusunan Kecuali Diri

この問題は線形時間と空間で解くのが簡単そうに見えます。この問題は、配列の基本的な概念のいくつかに基づいています。

1. 配列の走査。
2. プレフィックスとサフィックスの合計。

コーディング面接でこの質問をした企業は、Facebook、Amazon、Apple、Netflix、Google、Microsoft、Adobe、その他多くのトップテクノロジー企業です。

問題文

整数配列 nums を指定すると、answer[i] が nums[i] を除く nums のすべての要素の積と等しくなるような配列の回答を返します。

nums の接頭辞または接尾辞の積は、32 ビット 整数に収まることが保証されています。

除算演算を使用せずに、O(n) 時間で実行されるアルゴリズムを作成する必要があります。

テストケース #1:

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

テストケース #2:

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

問題を理解する

この問題は、線形時間と空間で解決する方が簡単に見えますが、疑似コードまたは実際のコード実装を作成する場合は注意が必要です。

図

4 つの要素を含む単純な配列から期待される結果を見てみましょう:

input = {1, 2, 3, 4}

したがって、各インデックスの値は、値自体を除く、配列内の他のすべての要素の積です。次の図はこれを示しています。

上の図に基づいて、公式を導き出すことができます。任意のインデックス i について、o から (i - 1) までの要素の積と (i + 1) から (N - 1) までの要素の積を使用して値を見つけることができます。これを次の図に示します。

思考プロセス

疑似コードを書く前に、質問を考えて面接官に質問してください。

1. 重複について心配する必要がありますか?
2. 配列が空であるか、要素が 1 つしかない場合はどうなりますか?期待される結果は何ですか?
3. 配列内のいずれかのインデックスの値 0 を考慮または無視する必要がありますか? 0 を含むインデックスを除き、他のすべての値は 0 になるためです。
4. この問題のコーナー/エッジケースは何ですか?

あなたと面接官が上記の質問について話し合ったら、問題を解決するためのさまざまなアプローチを考案してください。

1. 素朴なアプローチ/強引。
2. すべての要素の積。
3. 左右の商品です。
4. プレフィックスとサフィックスの合計。

アプローチ 1: ナイーブ/ブルートフォース

直感

総当たりアプローチを採用するには、2 つの for ループを実行する必要があります。外側のループのインデックスが内側のループのインデックス値と一致する場合、積をスキップする必要があります。それ以外の場合は、製品を続行します。

アルゴリズム

1. 変数を初期化します:
   • N = nums.length (入力配列の長さ).
   • result = new int[N] (結果を保存する配列).
2. 外側のループ (nums 内の各要素を反復処理):
   • i = 0 ～ N-1 の場合: currentProduct = 1 を初期化します。
3. 内部ループ (現在の要素の積を計算)、j = 0 ～ N-1 の場合:
   • i == j の場合、Continue を使用して現在の反復をスキップします。
   • currentProduct に nums[j] を掛けます。
   • currentProduct を result[i] に割り当てます。
4. 結果を返します。

コード

// 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;
}

複雑さの分析

1. 時間計算量: O(n^2)、外側ループと内側ループで配列を 2 回繰り返す場合。
2. 空間複雑度: O(n)、使用した補助空間 (result[] 配列)。

アプローチ 2: 配列の積 ❌

ほとんどの開発者が考える 1 つの方法は、すべての要素の積和を実行し、積和を各配列値で除算して結果を返すことです。

擬似コード

// 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 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;
}

配列要素の 1 つに 0 が含まれている場合はどうなりますか? ?

0 を含むインデックスを除くすべてのインデックスの値は必ず無限大になります。また、コードは java.lang.ArithmeticException.
をスローします。

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)

アプローチ 3: プレフィックスとサフィックスの積を検索する

プレフィックスとサフィックスの合計について詳しくは、私の Web サイト https://ggorantala.dev の配列マスタリー コースをご覧ください

直感と公式

プレフィックスとサフィックスは、結果のアルゴリズムを記述する前に計算されます。プレフィックスとサフィックスの合計の式を以下に示します:

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.

Atas ialah kandungan terperinci Leetcode : Produk Tatasusunan Kecuali Diri. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!