tags:
  - DSA

L6. Product of Array Except Self (Star)

Description

Given an integer array nums , return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs on time and without using the division operation.

Example1:

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Example2:

Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Solution

暴力方法需要循环遍历数组，时间复杂度来到了，不符合要求。

前缀积 + 后缀积时间复杂度空间复杂度都为。

#include <iostream>
#include <vector>

class mySolution{
public:
    std::vector<int> productExceptSelf(const std::vector<int> nums){
        std::vector<int> answer(nums.size());
        int prefix = 1;
        for(int i = 0; i < nums.size(); i++){
            answer[i] = prefix;
            prefix *= nums[i];
        }
        int suffix = 1;
        for(int i = nums.size() - 1; i >=0; --i){
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        return answer;
    }
};

int main(){
    std::vector<int> nums{1, 2, 3, 4};
    mySolution solution;
    std::vector<int> answer = solution.productExceptSelf(nums);
    for(auto elem : answer){
        std::cout << elem << std::endl;
    }
    return 0;
}