一道伤脑筋的算法题 亮了

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

原文发布于微信公众号 - Python与机器学习算法频道(alg-channel)

原文发表时间:2018-06-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

原生JS | 数据类型检测,并没你想象的那么简单

HTML5学堂-码匠:看上去,JavaScript中的数据类型检测,并没有什么难度,但是……它包含了不少的知识,如果你只知道一个typeof的话,那很建议你读读...

3425
来自专栏AzMark

Python字符串

1705
来自专栏blackheart的专栏

[程序设计语言]-[核心概念]-03:控制流

0.概述 前面介绍了语言的演进以及一些基础概念后,从本篇开始进入了语言的核心问题中。这一篇讨论的是语言计算模型(大致可以用控制流来表述),大致如下7种: 顺序执...

21310
来自专栏Leetcode名企之路

【Leetcode】58. 最后一个单词的长度

这个题比较水,主要是注意一下前后有空格这种情况。 如下代码用preLong记录截止到当前字符最后一个单词的长度.

1082
来自专栏非著名程序员

鸡蛋问题来了,是先有Class还是先有Object?

周末比较无聊,在浏览论坛的时候,偶然看到一个程序猿提问的问题,他时这样提问的:突然想到一个很菜的问题, 倒底先有Object还是先有Class?所有类都是Obj...

2076
来自专栏C语言C++游戏编程

C语言第一个字符串Hello,C语言基础教程之字符串

C 语言中,字符串实际上是使用 null 字符 '' 终止的一维字符数组。因此,一个以 null 结尾的字符串,包含了组成字符串的字符。

1232
来自专栏desperate633

设计模式之工厂方法模式(FACTORY METHOD)问题模拟工厂方法模式分析依赖倒置原则小结

工厂方法模式定义了一个创建对象的接口,但由子类决定要实例化的类是哪一个。工厂方法让类把实例化推迟到子类。 我们依然接着简单工厂模式提出的披萨店问题继续探讨

1024
来自专栏软件开发 -- 分享 互助 成长

希尔排序

1、希尔排序介绍 希尔排序是对直接插入排序算法的一种改进,当记录较少或者记录本身基本有序的时候直接插入排序的优势非常明显,所以希尔排序就是通过人为的创造这两个条...

2088
来自专栏程序员叨叨叨

6.8 控制流语句(Control Flow Statement)

程序最小的独立单元是语句(statement),语句一般由分号结尾,缺省情况下,语句是顺序执行的,但是当涉及逻辑判断控制时,就要求有控制流程序语句。控制流程序语...

2623
来自专栏深度学习自然语言处理

介绍4个大神常用而你不常用的python函数

1101

扫码关注云+社区

领取腾讯云代金券