LeetCode238除自身以外数组的乘积

发表于 | 分类于 |

题目描述

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

示例:

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

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

解题思路

本题是一道数组相关的题目。

因为不能用除法，只能用乘法，而一个元素的预期结果值是其两边元素的乘积，所以，可以使用两个数组来分别记录该元素左右数字的乘积。

算法实现

GitHub 上Python测试代码地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def productExceptSelf(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    size = len(nums)
    tmp = 1
    result = [1]
    for i in range(1, size):
        tmp *= nums[i - 1]
        result.append(tmp)
    tmp = 1
    for i in range(size - 2, -1, -1):
        tmp *= nums[i + 1]
        result[i] *= tmp
    return result