一天一大 leet

20200604

题目（难度：中等）：

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

示例

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

• 提示：

  1. 题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
  2. 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

抛砖引玉

分别计算当前数前后乘积之后相乘

例如：nums = [1,2,3,4,5]

• 假设当前数是 3 即 nums[2]
• left(2) = nums[0]*nums[1];
• right(2) = nums[4]*nums[5];
• 实现：循环得到 left(n)、right(n)
• 注意：
  • left 需要递增得到、right 需要递减得到
  • left[0]默认 1、right[nums.length]默认 1

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  let left = [1],
    right = [],
    result = []
  for (let i = 1; i < nums.length; i++) {
    left[i] = nums[i - 1] * left[i - 1]
  }
  // 得到right，这部分我没有给right[nums.length]赋默认值则可能会是undefined 所以增加了臃余的判断
  for (let i = nums.length; i >= 0; i--) {
    right[i] =
      (right[i + 1] !== undefined ? right[i + 1] : 1) *
      (nums[i + 1] !== undefined ? nums[i + 1] : 1)
  }
  // 得到result，这部分参考官方可进行优化省掉本次循环
  for (let i = 0; i < nums.length; i++) {
    result[i] = left[i] * right[i]
  }
  return result
}

官方答案

• 左右乘积列表

var productExceptSelf = function (nums) {
  const length = nums.length

  // L 和 R 分别表示左右两侧的乘积列表
  const L = new Array() < number > length
  const R = new Array() < number > length

  const answer = new Array() < number > length

  // L[i] 为索引 i 左侧所有元素的乘积
  // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
  L[0] = 1
  for (let i = 1; i < length; i++) {
    L[i] = nums[i - 1] * L[i - 1]
  }

  // R[i] 为索引 i 右侧所有元素的乘积
  // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
  R[length - 1] = 1
  for (let i = length - 2; i >= 0; i--) {
    R[i] = nums[i + 1] * R[i + 1]
  }

  // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
  for (let i = 0; i < length; i++) {
    answer[i] = L[i] * R[i]
  }

  return answer
}

• 空间复杂度 O(1)O(1) 的方法

var productExceptSelf = function (nums) {
  const length = nums.length
  const answer = new Array() < number > length

  // answer[i] 表示索引 i 左侧所有元素的乘积
  // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
  answer[0] = 1
  for (let i = 1; i < length; i++) {
    answer[i] = nums[i - 1] * answer[i - 1]
  }

  // R 为右侧所有元素的乘积
  // 刚开始右边没有元素，所以 R = 1
  let R = 1
  for (let i = length - 1; i >= 0; i--) {
    // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
    answer[i] = answer[i] * R
    // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
    R *= nums[i]
  }
  return answer
}

高手在民间

/**
 * @param {number[]} nums
 * @return {number[]}
 */
const productExceptSelf = (nums) => {
  const length = nums.length
  const result = []
  let k = 1
  // 一遍遍历获取每个元素左边的乘积数组
  for (let i = 0; i < length; i++) {
    result[i] = k
    k *= nums[i]
  }
  k = 1
  // 第二遍遍历乘以每个元素的所有右边元素得到最终值
  for (let i = length - 1; i >= 0; i--) {
    result[i] *= k
    k *= nums[i]
  }
  return result
}

菜鸡的自白

参考官方代码修改后代码

优化说明:

• 声明的返回数值 result 可以先存储 left，之后在其基础上直接计算结果
• 声明一个中间存储的变量来存储循环中 nums 迭乘的结果
• 使用 nums 迭乘分步与每个 left 值相乘得到 result
• 优化了：减少了判断和 left、right 的声明

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  let result = [1],
    rightMiddleValue = 1
  for (let i = 1; i < nums.length; i++) {
    result[i] = nums[i - 1] * result[i - 1]
  }
  for (let i = nums.length - 1; i >= 0; i--) {
    result[i] = result[i] * rightMiddleValue
    rightMiddleValue *= nums[i]
  }
  return result
}

博客: 小书童博客
公号: 坑人的小书童