」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > Typescript 編碼編年史: Self 以外的陣列的乘積

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

發佈於2024-07-31
瀏覽:903

Typescript Coding Chronicles: Product of Array Except Self

问题陈述:

给定一个整数数组nums,返回一个数组answer,使得answer[i]等于除nums[i]之外的nums所有元素的乘积。

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) 额外的空间复杂度解决这个问题吗? (输出数组不计为空间复杂度分析的额外空间。)

初步思考过程:

为了解决这个问题,我们需要计算除当前元素之外的所有元素的乘积,而不使用除法运算。这可以通过对数组使用两次传递来完成:

  1. 计算每个元素的前缀积。
  2. 计算每个元素的后缀乘积并与前缀乘积相乘。

基本解决方案:

我们可以用两个数组来存储前缀和后缀的乘积,然后将它们相乘得到最终的结果。

代码:

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 = 0; i--) {
        suffixProducts[i] = suffixProducts[i   1] * nums[i   1];
    }

    // Compute the result by multiplying prefix and suffix products
    for (let i = 0; i 



时间复杂度分析:

  • 时间复杂度: 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 = 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}

时间复杂度分析:

  • 时间复杂度: O(n),其中n是数组的长度。我们迭代数组两次。
  • 空间复杂度: O(1),因为我们使用输出数组来存储中间结果并且不使用任何额外的空间。

基本解决方案的改进:

  • 优化后的解决方案通过使用中间结果的输出数组将空间复杂度降低到 O(1)。

边缘情况和测试:

边缘情况:

  1. 数组包含零。
  2. 数组包含负数。
  3. 数组长度为最小 (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]

一般解决问题的策略:

  1. 理解问题:仔细阅读问题陈述,了解需求和约束。
  2. 识别关键操作:确定需要的关键操作,例如计算前缀和后缀乘积。
  3. 优化可读性:使用清晰简洁的逻辑,确保代码易于理解。
  4. 彻底测试:使用各种情况(包括边缘情况)测试解决方案,以确保正确性。

识别类似问题:

  1. 前缀和数组:

    • 需要计算范围查询的前缀和的问题。
    • 示例:范围求和查询。
  2. 就地算法:

    • 需要在有限的额外空间内进行操作的问题。
    • 示例:将数组向右旋转 k 步。
  3. 数组操作:

    • 需要根据具体情况修改数组的问题。
    • 示例:将零移至数组末尾。

结论:

  • 使用额外空间的基本方法和优化的就地方法可以有效地解决计算除 self 之外的数组的乘积的问题。
  • 理解问题并将其分解为可管理的部分至关重要。
  • 使用清晰的逻辑并优化可读性可确保解决方案易于理解。
  • 使用各种边缘情况进行测试可确保稳健性。
  • 认识问题的模式可以帮助将类似的解决方案应用于其他挑战。

通过练习这些问题和策略,您可以提高解决问题的能力,并为各种编码挑战做好更好的准备。

版本聲明 本文轉載於:https://dev.to/__zamora__/typescript-coding-chronicles-product-of-array-except-self-3gg4?1如有侵犯,請聯絡[email protected]刪除
最新教學 更多>

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3