Description
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].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
描述
给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。
进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)
思路
- 声明一个结果数组res,用于返回结果.
- 我们首先正向遍历数组,获取当前位置左边的数的所有乘积,即
也就是
- 我们声明一个辅助变量_product用于记录当前位置右边的所有数字的乘积,于是根据定义,位置i的值为(i左边所有数的乘积)与(i右边所有数的乘积)的乘积.
- 所以res[i]= res[i](i左边所有数的乘积)*_product(i右边所有数的乘积),然后我们更新_product *= nums[i].
# -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2019-02-02 08:52:08 # @Last Modified by: 何睿 # @Last Modified time: 2019-02-02 09:01:08 class Solution: def productExceptSelf(self, nums): """ :type nums: List[int] :rtype: List[int] """ # 声明结果数组,第一个位置(索引0)一定要初始化为1 res = [1 for _ in range(len(nums))] # 辅助变量 _product = nums[-1] # 正向遍历,获取当前位置左边的所有数字乘积的值 for i in range(1, len(nums)): res[i] = res[i - 1] * nums[i - 1] # 反向遍历,_product表示当前位置右边的数所有乘积的值 for i in range(len(nums) - 2, -1, -1): # 当前位置的值等与当前位置左右两边所有数的乘积 res[i] = _product * res[i] _product *= nums[i] # 返回结果 return res
源代码文件在这里.