每日题解:LeetCode 238. 除自身以外数组的乘积

Author Avatar
清水雅然君 06月 04,2020

题目地址

题目描述

给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。

说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

解法

JAVA

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

解题思路

  • 左右指针
    刚开始的想法,使用左右指针解法,从左边遍历乘积left到K,然后从数组的右边的遍历积right到K,然后左右的乘积left*right作为K的,即[k]=left*right
  • 利用数组
    假设我要求K+1的值,只需要将之前的left*K* (right(K+2))(right(K+1))是K+1下标右边的乘积,先暂时不计算这个值,我们先考虑K+1的左边,这样就没必要每次从左往右,从那就从左往右遍历一遍是数组,k+1的下标记录从0到K的乘积就好了。
 int len = nums.length;
int[] left = new int[len];

由于K+1的位置记录到K的乘积,所以需要一个变量错开

 int k = 1;
 //由于下标为0的左边的乘积没有,我们记录为1
for (int i = 0; i < len; i++) {
//先赋值,比如0下标的就记录为1
left[i]= k;
//然后乘积当前的值,赋值给i+1
k*=nums[i];
}

此时left[]数组记录了从左到右每个下标的乘积,我们以[1,2,3,4]为例,从此时left[]的值为[1,1,2,6]
然后我们计算从右到左的乘积,
下标3时,1*6
下标2时,4*2
下标1时,34*1
下标0时,3
4*2*1
红色标记为left的下标的值,此时,i的位置的答案(i+1)*(i+2)...*(len)*left[i]
那么只要从右往左进行遍历,然后变量记录i位置右边的乘积,然后和left[i]`相乘

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