Typescript 編碼編年史： Self 以外的陣列的乘積-js教程-PHP中文網

Typescript 編碼編年史： Self 以外的陣列的乘積

王林

發布： 2024-07-17 11:38:48

原創

695 人瀏覽過

Typescript Coding Chronicles: Product of Array Except Self

問題陳述：

給定一個整數數組 nums，傳回一個數組 answer，使得 answer[i] 等於 nums 中除 nums[i] 之外的所有元素的乘積。

nums 的任何前綴或後綴的乘積保證適合 32 位元整數。

您必須編寫一個在 O(n) 時間內運作且不使用除法運算的演算法。

範例1：

輸入：nums = [1,2,3,4]
輸出：[24,12,8,6]

範例2：

輸入：nums = [-1,1,0,-3,3]
輸出：[0,0,9,0,0]

限制條件：

2
-30
nums 的任何前綴或後綴的乘積保證適合 32 位元整數。

後續：

你能以 O(1) 額外的空間複雜度解決這個問題嗎？（輸出數組不計為空間複雜度分析的額外空間。）

初步思考過程：

為了解決這個問題，我們需要計算除當前元素之外的所有元素的乘積，而不使用除法運算。這可以透過對數組使用兩次傳遞來完成：

計算每個元素的前綴積。
計算每個元素的後綴乘積並與前綴乘積相乘。

基本解決方案：

我們可以使用兩個陣列來儲存前綴和後綴的乘積，然後將它們相乘得到最終結果。

代碼：

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const prefixProducts = new Array(n).fill(1);
    const suffixProducts = new Array(n).fill(1);
    const result = new Array(n).fill(1);

    // Compute prefix products
    for (let i = 1; i < n; i++) {
        prefixProducts[i] = prefixProducts[i - 1] * nums[i - 1];
    }

    // Compute suffix products
    for (let i = n - 2; i >= 0; i--) {
        suffixProducts[i] = suffixProducts[i + 1] * nums[i + 1];
    }

    // Compute the result by multiplying prefix and suffix products
    for (let i = 0; i < n; i++) {
        result[i] = prefixProducts[i] * suffixProducts[i];
    }

    return result;
}

登入後複製

時間複雜度分析：

時間複雜度： O(n)，其中 n 是陣列的長度。我們迭代數組三次。
空間複雜度： O(n)，用於儲存前綴和後綴乘積。

限制：

基本解決方案效果很好，但需要額外的空間來儲存前綴和後綴產品。

優化方案：

我們可以最佳化解決方案以使用 O(1) 額外空間，方法是使用輸出陣列首先儲存前綴產品，然後就地修改它以包含後綴產品。

代碼：

function productExceptSelfOptimized(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(1);

    // Compute prefix products in the result array
    for (let i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Compute suffix products and multiply with the prefix products
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}

登入後複製

時間複雜度分析：

時間複雜度： O(n)，其中 n 是陣列的長度。我們迭代數組兩次。
空間複雜度： O(1)，因為我們使用輸出陣列來儲存中間結果，而不使用任何額外的空間。

基本解決方案的改進：

最佳化的解決方案透過使用輸出數組作為中間結果，將空間複雜度降低到 O(1)。

邊緣情況和測試：

邊緣情況：

陣列包含零。
陣列包含負數。
陣列長度是最小（2）或最大（10^5）限制。

測試用例：

console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelf([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelf([0,0])); // [0,0]
console.log(productExceptSelf([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelf([1,2])); // [2, 1]

console.log(productExceptSelfOptimized([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelfOptimized([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelfOptimized([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelfOptimized([0,0])); // [0,0]
console.log(productExceptSelfOptimized([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelfOptimized([1,2])); // [2, 1]

登入後複製