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