首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一道伤脑筋的算法题 亮了

一道伤脑筋的算法题 亮了

作者头像
double
发布2018-07-31 17:26:15
2970
发布2018-07-31 17:26:15
举报
文章被收录于专栏:算法channel算法channel
2018 06 15

题目没看懂?

一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 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

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-06-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员郭震zhenguo 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档