Typescript 编码编年史：除 Self 之外的数组的乘积-js教程-PHP中文网

Typescript 编码编年史：除 Self 之外的数组的乘积

王林

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

原创

628 人浏览过

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]

登录后复制