友链
姚屹晨

leetcode - [238] Product of Array Except Self

2020/04/24

题目描述

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

给你一个整数数组，该数组的个数保证大于1，计算每个元素其余元素乘积。

举个例子：

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

Update at 2020_0625

解法2非常惊艳，让我们重新理解一下：

首先，我们需要一个存放最终结果的数组ans。

然后，从左往右依次计算当前元素左侧的乘积。

int l = 1;
for (int i = 0; i < len; i++){
    ans[i] = l;
    l *= nums[i];
}

接着，仍使用ans数组，依次从右往左计算当前元素右侧的乘积。

int r = 1;
for (int i = len - 1; i >= 0; i--){
    ans[i] *= r;
    r *= nums[i];
}

来看下完整实现：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        int   len = nums.length;
        int[] ans = new int[len];
        
        int l = 1;
        for (int i = 0; i < len; i++){
            ans[i] = l;
            l *= nums[i];
        }
        
        int r = 1;
        for (int i = len - 1; i >= 0; i--){
            ans[i] *= r;
            r *= nums[i];
        }
        
        return ans;
    }
}

解法1

我的想法是这样的：先将数组中所有整数相乘，然后除以当前元素。

public int[] productExceptSelf(int[] nums) {
    int length = nums.length;
    int[] ret = new int[length];
    int product = 1;
    for (int n: nums){
        product *= n; 
    }
    for (int i = 0; i < length; i++){
        ret[i] = product / nums[i];
    }
    return ret;
}

一旦数组中出现0，上面的方法就行不通。

那我们就考虑下，数组中出现0的几种情况：

第一种，只有一个0，举个例子： [1, 0, 2]，此时应该返回[0, 2, 0]。

也就是说，我们只需要乘积非零元素，然后将其放在索引为0的位置即可。

第二种，大于一个0，举个例子： [1, 0, 2, 0]，此时应返回[0, 0, 0, 0]。

很明显，这种场景数组中的元素全部都是0，也就是初始化的数组。

让我们来调整一下代码：

public int[] productExceptSelf(int[] nums) {
    int length = nums.length;
    int[] ret = new int[length];
    int product = 1;
    int singleFlag = 0;
    List<Integer> zeroList = new ArrayList<>();
    for (int i = 0; i < length; i++){
        if (nums[i] == 0){
            singleFlag++;
            zeroList.add(i);
        } else {
            product *= nums[i];             
        }
    }
    if (singleFlag == 0){
        for (int i = 0; i < length; i++){
            ret[i] = product / nums[i];
        }
    } else if (singleFlag == 1){
        ret[zeroList.get(0)] = product;
    }
    
    return ret;
}

解法2

Thanks @lycjava3 and @kingsizebeast

这种方法的关键在于，两次遍历，分别乘积当前元素之前与之后的元素。

public int[] productExceptSelf(int[] nums) {
    int len = nums.length;
    int[] res = new int[len];
    int left = 1;
    for (int i = 0; i < len; i++){
        if (i > 0){
            left *= nums[i - 1];
        }
        res[i] = left;
    }
    
    int right = 1;
    for (int j = len - 1; j >= 0; j--){
        if (j < len - 1){
            right *= nums[j + 1];
        }
        res[j] *= right;
    }
    return res;
}

注意以下两点：

1、 若需要乘积左边的元素，则left *= nums[i - 1]。

2、 若需要乘积右边的元素，则right *= nums[j + 1]。

Enjoy it!


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory