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

double

发布于 2018-07-31 17:25:10

7510

发布于 2018-07-31 17:25:10

文章被收录于专栏：算法channel

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 解题小结

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