题目描述:
- 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.)
代码实现(个人版):
- class Solution:
- def productExceptSelf(self, nums):
- length = len(nums)
- left, right = 1, 1
- m, n = 0, 0
- aux = []
- while m < length:
- aux.append(right)
- right *= nums[-m-1]
- m += 1
- while n < length:
- aux[-n-1] = left * aux[-n-1]
- left *= nums[n]
- n += 1
- return aux[::-1]
- if __name__ == '__main__':
- x = [1, 2, 3, 4]
- y = Solution().productExceptSelf(x)
- print(y)
分析(个人版):
题目要求: 不能使用除法; 必须在 O(n)时间内完成; 在常数空间复杂度的范围内完成且输出序列不占用额外的空间复杂度.
基于以上考虑, 得到以下思路:
(1)首先不能做重复的乘法运算, 否则时间复杂度必然不能满足;
(2)题目的特点是以 nums[i]为界将其分为左右两部分的, 因此可以考虑 "分而治之": 定义一个左累乘器 left 和右累乘器 right, 指针 i 从左向右依次滑过 nums 的每个位置, left 随着 i 的滑动依次乘以 nums 中的下一个元素. right 是 left 的镜像, 相当于随着虚拟指针 j(实际并不存在)从右向左滑动时依次乘以从右向左的下一个元素. 这样当指针 i 和 j 滑遍整个 nums 数组时, 就得到了 output 数组中所有位置需要的所有因式项, 而且大大减少了重复乘法运算的次数;
(3)对于空间复杂度的考量: 由于输出序列不占用额外的空间复杂度, 因此不妨让输出序列 (即代码中的 aux 列表) 充当额外需要的空间, 这样就可以满足空间复杂度的要求;
(4)在代码中的第二个 while 循环结束之后, aux 中保存的结果是反过来的(这是出于对尽量节省空间的考虑, 尽量只使用 aux 这一个额外的空间), 因此最终 return 时要再对其进行逆序.
由 list 引发的 runtime 和 memory cost 的一点分析:
上述个人版的 runtime 和 memory cost 为:
如果将上述代码的第 6-8 行改为以下方式而其他地方不变:
- aux = [0] * length
- while m < length:
- aux[m] = right
则 runtime 和 memory cost 将会变为:
由此可见, 在新建一个 list 时, 如果能事先指定 list 的长度, 那么代码的运行时间和所消耗的空间都将会有所改善.
代码实现(大神版):
- class Solution(object):
- def productExceptSelf(self, nums):
- """
- :type nums: List[int]
- :rtype: List[int]
- """
- ans = [1] * len(nums) # 首先定义一个长度为 len(nums)且全为 1 的 list, 为第一个 for 循环中的左累乘做准备
- for i in range(1, len(nums)): # 左累乘
- ans[i] = ans[i - 1] * nums[i - 1] # 每次运算后, ans 的第 i 个位置保存的都是 nums 中第 i 个位置之前的所有因子的积
- right = 1
- for i in range(len(nums) - 1, -1, -1): # 逆序的目的是为了计算右累乘
- ans[i] *= right # 左右累乘之积即为最终的结果
- right *= nums[i] # 右累乘
- return ans
大神版代码分析:
核心思想也是利用左累乘器和右累乘器.
一些示意图如下:
大神版代码运行结果:
来源: http://www.bubuko.com/infodetail-3070941.html