238. Product of Array Except Self

Leetcode 问题: 238. Product of Array Except Self
Categories:
Tags:

题目

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

传入整数阵列 nums，回传一个整数阵列，上面的阵列索引结果是，每个元素除了自己以外，的乘法总和

传入数字的乘法合保证是 32-bit 整数

必须写一个演算法，时间複杂度是 O(n)，且没有使用除法去去求得数字

PS: 除法方式是，计算完整个阵列的乘法合，然后除以索引数字，就可以得到该元素排除自己的乘法合

Example

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

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

演算法

1. 不使用额外空间去储存乘法结果

仅使用一个阵列去储存答案，不额外使用空间储存答案

2. 从前方 i = 0 计算每个数字的 prefix 前方所有乘法合数字

第一个数字前面没有 prefix 数字，所以预设为 1，1 乘以任何数不会对任何数做异动

数字阵列 [1,2,3,4] prefix 乘法合

数字 1 2 3 4
prefix 前缀乘法合 1 1 2 6
prefix 运算 1 (无前缀，预设 1) 1 1 * 2 1 * 2 * 3

将这个运算结果纪录在结果的阵列，然后继续加上 postfix 后面数字乘法合

2. 从后方 i = length -1 计算每个数字的 postfix 后方所有乘法合数字

最后一个数字后面没有 postfix 数字，所以预设为 1，1 乘以任何数不会对任何数做异动

数字阵列 [1,2,3,4] postfix 乘法合

数字 1 2 3 4
postfix 后缀乘法合 24 12 4 1
postfix 运算 2 * 3 * 4 3 * 4 4 1 (无后缀，预设 1)
prefix 前缀乘法合 1 1 2 6
prefix 运算 1 (无前缀，预设 1) 1 1 * 2 1 * 2 * 3
prefix 与 postfix 乘法合 24 12 8 6
prefix 与 postfix 运算 1 * 2 * 3 * 4 1 * 3 * 4 1 * 2 * 4 1 * 2 * 3 * 1

最后会发现，直接将 prefix 运算完的乘法合，直接乘以 postfix 的乘法合，就可以获得最后的答案了 [24,12,8,6]

答案

JavaScript

function productExceptSelf(numsList) {
    // 建立一个乘法的结果阵列
    var numsProductResult = new Array(numsList.length);
    // prefix 总和，第一个数字前面没有 prefix，预设为 1，1 乘以任何数不会对任何数做异动
    var prefixNumProduct = 1;
    for (var i = 0; i < numsList.length; i++) {
        var currentNumber = numsList[i];
        // 设定目前数字的 prefix 数字「乘法总合」
        numsProductResult[i] = prefixNumProduct;
        // 设定目前数字的乘法总和，给下一个数字当作 prefix 使用
        prefixNumProduct = prefixNumProduct * currentNumber;
    }
    // postfix 总和，最后一个数字后面没有 postfix，预设为 1，1 乘以任何数不会对任何数做异动
    var postfixNumProduct = 1;
    for (var i = numsList.length - 1; i >= 0; i--) {
        var currentNumber = numsList[i];
        // 设定目前数字的 prefix 与 postfix 的「乘法总合」
        numsProductResult[i] = numsProductResult[i] * postfixNumProduct;
        // 设定目前数字的乘法总和，给下一个数字当作 postfix 使用
        postfixNumProduct = postfixNumProduct * currentNumber;
    }
    return numsProductResult;
}

TypeScript

function productExceptSelf(numsList: number[]): number[] {
    // 建立一个乘法的结果阵列
    let numsProductResult = new Array(numsList.length);

    // prefix 总和，第一个数字前面没有 prefix，预设为 1，1 乘以任何数不会对任何数做异动
    let prefixNumProduct = 1;

    for (let i = 0; i < numsList.length; i++) {
        let currentNumber = numsList[i];
        // 设定目前数字的 prefix 数字「乘法总合」
        numsProductResult[i] = prefixNumProduct;
        // 设定目前数字的乘法总和，给下一个数字当作 prefix 使用
        prefixNumProduct = prefixNumProduct * currentNumber;
    }

    // postfix 总和，最后一个数字后面没有 postfix，预设为 1，1 乘以任何数不会对任何数做异动
    let postfixNumProduct = 1;
    for (let i = numsList.length -1; i >=0; i--) {
        let currentNumber = numsList[i];
        // 设定目前数字的 prefix 与 postfix 的「乘法总合」
        numsProductResult[i] = numsProductResult[i] * postfixNumProduct;
        // 设定目前数字的乘法总和，给下一个数字当作 postfix 使用
        postfixNumProduct = postfixNumProduct * currentNumber;
    }

    return numsProductResult;
};

参考资料