题目没看懂?
一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1).
举个例子:
输入:2, 3, 5, 1
输出:15, 10, 6, 30
分析:
15 = 3 * 5 *1; 10 = 1 * 5 * 1; 6 = 2 * 3 * 1;30 = 2 * 3 * 5
解题思路
昨晚,公号内发出请求后,群内小伙伴积极参与讨论。截止目前,共收到 2 份完整代码,都是正确的。
根据题意:res[i] = a[0] * a[1] * ... * a[i-1] * a[i+1] *...*a[n-1] . 标记 p[i] 为索引 0 到 i-1 的元素累乘,s[i] 为索引 i+1 到 n-1 的元素累乘,因此,res[i] = p[i] * s[i] .
代码实现思路,遍历a数组,得到任意索引 i 的累乘,注意此处缓存是为接下来再遍历a,使用 p[i] * s[i] 做铺垫,如代码1所示。
代码1
def fun(a):
p = [1]
s = [1]
la = len(a)
for i in range(1,la):
p.append(p[i-1] * a[i-1]) # p[i] = p[i-1] * a[i-1]
s.append(s[i-1] * a[la-i] ) # s[i] = s[i-1] * a[la-i]
for i in range(la):
p[i] *= s[la - i -1]
return p
cuma = fun([2,3,5,1,2])
此版本时间复杂度为O(n),但是空间复杂度为O(n). 与题目要求的空间复杂度为O(1)不符。
下面这版,思想与代码1相同,但是更节省空间,空间复杂度为O(1). 技巧大家自己体会下。
代码2
int * cal(int *input, int n)
{
int i;
int *result = new int[n];
result[0] = 1;
for (i = 1; i < n; ++i)
{
result[i] = result[i - 1] * input[i - 1];
}
result[0] = input[n - 1];
for (i = n - 2; i > 0; --i)
{
result[i] *= result[0];
result[0] *= input[i];
}
return result;
}
以上代码由互助群1 软件工程-陈志豪提供,欢迎与我联系,领取 Gitchat 动态规划邀请卡。有兴趣的可参考:
http://gitbook.cn/gitchat/activity/5b173ce1e4e6d50625638322