題目： LeetCode - 238. Product of Array Except Self

題目說明

給一個陣列 nums，要求回傳一個陣列 res，res[i] 的值為除了 nums[i] 以外，其他所有位於 nums 的元素的乘積。

解題思路

  • 解法一：定義一個 index 起始值為 - 1，訪問 nums 內所有元素，當碰到 0 時，把 index 儲存，若再碰到 0，則代表整個 res 都是 0，可以直接回傳。若只有 1 個 0，則 res[index] = all，其餘都為 0，否則 res[i] = all / nums[i]。

  • 解法二：對於 res 來說，res[i] = (nums[0] * nums[1] * ... * nums[i - 1]) * (num[nums.size() - 1] * num[nums.size() - 2] * ... * nums[i + 1])，所以使用一個陣列計算右邊的部分，左邊的部分直接在迴圈做即可得到 res。

參考解法

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size(), all = 1, index = -1;
        vector<int> res(n, 0);
        for(int i = 0; i < n; ++i)
            if(nums[i] != 0)
                all *= nums[i];
            else if(index == -1)
               index = i;
            else
                return res;
        if(index == -1)
            for(int i = 0; i < n; ++i)
                res[i] = all / nums[i];
        else
            res[index] = all;
        return res;
    }
};

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> rightProduct(n, 1);
        for(int i = n - 2; i >= 0; --i)
            rightProduct[i] = rightProduct[i + 1] * nums[i + 1];
        for(int i = 0, left = 1; i < n; left *= nums[i], ++i)
            rightProduct[i] *= left;
        return rightProduct;
    }
};