算法刷题目数组和矩阵
Source
Edit
History

不包含本位置值的累乘数组

不包含本位置值的累乘数组

一、题目

给定一个整形数组 arr，返回不包含本位置值的累乘数组

例如：

1
2
arr = [2, 3, 1, 4]
返回 [12, 8, 24, 6]，即除自己外，其他位置上的累乘

二、思路

可以使用除法，即求出数组中所有数的乘积，然后结果数组中每一位上的数值即为：总乘积 / 当前位置元素。不过这种方法要注意数组中包含 0 的情况。

  • 如果数组中有一个 0 ，对唯一的 arr[i] == 0 的位置令 res[i] = all，其他位置全为 0 即可
  • 如果数组中 0 的数量大于 1，那么 res 所在位置上的值都是 0

在介绍第二种做法。

  1. 生成两个长度和 arr 一样的新数组 lr 和 rl。lr 表示从左到右的累乘，即：lr[i] = arr[0 ... i] 的累乘。rl 表示从右到左的累乘，即：rl[i] = arr[i ... N-1] 的累乘。
  2. 一个位置上除去自己值的累乘，就是自己左边的累乘再乘以自己右边的累乘，即 res[i] = lr[i-1] * rl[i+1]
  3. 最左位置和最右位置的累乘比较特殊，即 res[0] = rl[1], res[N-1] = lr[N-2]

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <vector>

class Solution {
public:
    std::vector<int> get_product(const std::vector<int>& arr) {
        if (arr.size() < 2) {
            return arr;
        }
        int count = arr.size();
        std::vector<int> res(count, 0);
        std::vector<int> left_product(count, 0);
        std::vector<int> right_product(count, 0);
        left_product[1] = arr[0];
        for (int i = 2; i < count; ++i) {
            left_product[i] = left_product[i-1] * arr[i-1];
        }
        right_product[count-2] = arr[count-1];
        for (int i = count-3; i >= 0; --i) {
            right_product[i] = right_product[i+1] * arr[i+1];
        }
        res[0] = right_product[0];
        res[count-1] = left_product[count-1];
        for (int i = 1; i < count-1; ++i) {
            res[i] = left_product[i] * right_product[i];
        }
        return res;
    }

    std::vector<int> get_product2(const std::vector<int>& arr) {
        if (arr.empty() || arr.size() < 2) {
            return std::vector<int>();
        }
        int count = 0;
        int all = 1;
        for (int i = 0; i < arr.size(); ++i) {
            if (arr[i] != 0) {
                all *= arr[i];
            } else {
                count++;
            }
        }
        std::vector<int> res(arr.size(), 0);
        if (count == 0) {
            for (int i = 0; i < arr.size(); ++i) {
                res[i] = all / arr[i];
            }
        }
        if (count == 1) {
            for (int i = 0; i < arr.size(); ++i) {
                if (arr[i] == 0) {
                    res[i] = all;
                }
            }
        }
        return res;
    }

    std::vector<int> get_product3(const std::vector<int>& arr) {
        if (arr.empty() || arr.size() < 2) {
            return std::vector<int>();
        }
        std::vector<int> res(arr.size(), 0);
        res[0] = arr[0];
        for (int i = 1; i < arr.size(); ++i) {
            res[i] = res[i-1] * arr[i];
        }
        int tmp = 1;
        for (int i = arr.size() - 1; i > 0; --i) {
            res[i] = res[i-1] * tmp;
            tmp *= arr[i];
        }
        res[0] = tmp;
        return res;
    }
};

int main() {
    Solution s;
    std::vector<int> arr{2, 3, 1, 4};
    auto res = s.get_product3(arr);
    for (const auto& x : res) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    return 0;
}