代码拉取完成,页面将自动刷新
同步操作将从 光花梗虎耳草/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个长度为 n 的整数数组 nums
,其中 n > 1,返回输出数组 output
,其中 output[i]
等于 nums
中除 nums[i]
之外其余各元素的乘积。
示例:
[1,2,3,4]
提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。
进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
output = [1 for _ in nums]
left = right = 1
for i in range(n):
output[i] = left
left *= nums[i]
for i in range(n - 1, -1, -1):
output[i] *= right
right *= nums[i]
return output
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] output = new int[n];
for (int i = 0, left = 1; i < n; ++i) {
output[i] = left;
left *= nums[i];
}
for (int i = n - 1, right = 1; i >= 0; --i) {
output[i] *= right;
right *= nums[i];
}
return output;
}
}
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
const n = nums.length;
let output = new Array(n);
for (let i = 0, left = 1; i < n; ++i) {
output[i] = left;
left *= nums[i];
}
for (let i = n - 1, right = 1; i >= 0; --i) {
output[i] *= right;
right *= nums[i];
}
return output;
};
利用前缀和思想,分别求出 i
左右两侧的乘积
func productExceptSelf(nums []int) []int {
n := len(nums)
l := make([]int, n)
l[0] = 1
for i := 1; i < n; i++ {
l[i] = l[i-1] * nums[i-1]
}
r := make([]int, n)
r[n-1] = 1
for i := n - 2; i >= 0; i-- {
r[i] = r[i+1] * nums[i+1]
}
ans := make([]int, n)
for i := 0; i < n; i++ {
ans[i] = l[i] * r[i]
}
return ans
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。