除自身累乘算法题,又有创意解法了

2018 06 16

除自身相乘

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

1 算法代码

昨晚,公号内推送了这道题的两版算法代码。推出后,又有小伙伴@地球村长 精心整理这道题详细的分析过程,如何一步一步解决除自身相乘问题。

今天凌晨近4点,@zero 估计观看西班牙和葡萄牙比赛中,给我发了一版堪称C罗神一般的电梯球那样的解法---深度优先搜索求解。

十分感谢@地球村长,@zero. 大家继续领悟这道:除自身相乘的算法题,彻底分析透,感受算法的魅力所在。

这道题主要难度在于时间复杂度和空间复杂度的要求,下面由浅入深的分析这道题:

v1 时间复杂度 O(n^2), 空间复杂度 O(1)

def product_except_self1(lst):

    n = len(lst)

    if n == 0:
        return 0

    if n == 1:
        return lst[0]

    res = [1 for i in range(n)]


    for i in range(n):
        for j in range(n):
            if j == i:
                continue
            else:
                res[i] *= lst[j]

    return res

print(product_except_self1([1,2,3,4]))

v2 时间复杂度 O(n), 空间复杂度 O(n)

def product_except_self2(lst):
    n = len(lst)
    if n == 0:
        return 0
    if n == 1:
        return lst[0]

    res = [1 for i in range(n)] # 保存结果的数组
    fwd = [1 for i in range(n)]
    bwd = [1 for i in range(n)]


    for i in range(1,n):
        fwd[i] = fwd[i-1] * lst[i-1]

    for i in range(n-2, -1, -1):
        bwd[i] = bwd[i+1] * lst[i+1]


    for i in range(n):
        res[i] = fwd[i] * bwd[i]

    return res

print(product_except_self2([1,2,3,4]))

v3 时间复杂度 O(n), 空间复杂度 O(1)

def product_except_self3(lst):
    n = len(lst)
    if n == 0:
        return 0

    if n == 1:
        return lst[0]

    res = [1 for i in range(n)] # 保存结果的数组


    for i in range(1,n):
        res[i] = res[i-1] *lst[i-1] # 从前往后遍历,以每个元素为界,之前元素累乘

                                    # 每次利用lst累乘一个结果(主要考虑空间复杂度)

    temp = lst[n-1] # 保存最后一个元素
    for i in range(n-2, -1, -1): # 从后往前遍历,以每个元素为界,之后元素累乘
        res[i] = res[i] * temp # 每次利用lst累乘一个结果(主要考虑空间复杂度)
        temp = temp * lst[i]
    return res

print(product_except_self3([1,2,3,4]))

v4 时间复杂度 O(n), 空间复杂度 O(1),直接拿输入数组保存结果,深度优先搜索,往下递推更新前缀积,回溯时更新后缀积。

using namespace std;
const int N = 1e4 + 5;
int f[N], n;
void dfs(int pre, int now, int& suf) {
    if(now == n + 1)
           return;
 dfs(pre * f[now], now + 1, suf);
    int t = f[now];
    f[now] = pre * suf;
    suf *= t;
}
int main() {
 cin >> n;
 for(int i = 1; i <= n; i++)
     cin >> f[i];
 int x = 1;
 dfs(1, 1, x);
 for(int i = 1; i <= n; i++)
     cout << f[i] << " ";
}

2 解题小结

数据结构与算法的优化主要有两个方面:

  1. 数据结构上的优化: 如:2与1相比得到常用:以空间换时间。

还有其他常用的是以字典来代替数组,这是数据结构上的优化

2. 算法上的优化:

如3与2相比得到:迭代和分治的思想。

还有常用的二分法与暴力法查找的比较这是算法上的优化

3. 面试经验小结:

  • 一般大公司面试都有比较规范的流程
  • 数据结构与算法写代码一般从易到难,逐步深入
  • 第一题,如果没有思路,尝试用 “二分+快排”(能解决70%的问题),所以不要说你不知道怎么准备面试,二分、快排及变形会了吗?
  • 算法难度到动态规划吧,校招一般过了较难的动态规划题,很可能要你了,算法基本思想会了吗?
  • 最后希望多刷题 leetcode,中文链接(省去英文读题):https://leetcode-cn.com/problemset/all/

4. 以上只是本人经验总结,不可绝对化,谢谢支持。

5. 感谢群组郭大哥的支持、鼓励与分享!

作为奖励,@地球村长,@zero ,欢迎与我联系,领取 Gitchat 动态规划邀请卡(2.99元)。本场 chat 的入口:

http://gitbook.cn/gitchat/activity/5b173ce1e4e6d50625638322

3 邀请进群

以上错误之处,有疑问的地方,或者待优化改进之处,欢迎公号内留言、微信群内提问作者。

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣学算法

数据结构学习秘籍

网络上太多的同学吐槽被虐,如滔滔江水连绵不绝,数据结构太难了!真的很难吗?其实数据结构只是讲了三种:线性结构、树、图。到底难在哪里呢?通过调查了解大概有四个原因...

1202
来自专栏前端新视界

一道看似非常难的面试算法题

这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等(感谢博友提供的关于该问题的相关资料 划分问题)。由于时间仓促,加之面试时头昏脑涨,这道题...

2538
来自专栏aCloudDeveloper

算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

28810
来自专栏数据结构与算法

P1796 汤姆斯的天堂梦_NOI导刊2010提高(05)

题目描述 汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣,每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。 有一些航班将...

2828
来自专栏chenjx85的技术专栏

leetcode-53-Maximum Subarray(动态规划详解)

2164
来自专栏云时之间

算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个...

1282
来自专栏ACM算法日常

POJ2318 TOYS 判断点与直线位置关系 【计算几何】

Calculate the number of toys that land in each bin of a partitioned toy box.

1113
来自专栏C语言及其他语言

初学C语言的学习计划

背景:很多同学在学习C语言的过程中,常常会遇到这样的问题,即“教材看完了,知识点也懂,但写不出来程序”,这段时间,我们通过长期与有多年C语言研究经验的教授、教师...

3684
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列02:替换空格 原

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1273
来自专栏数据结构与算法

P1488 肥猫的游戏

题目描述 野猫与胖子,合起来简称肥猫,是一个班的同学,他们也都是数学高手,所以经常在一起讨论数学问题也就不足为奇了。一次,野猫遇到了一道有趣的几何游戏题目,便拿...

4237

扫码关注云+社区

领取腾讯云代金券