Написано: 18.03.2023
238. Произведение массива, кроме элемента (Product of Array Except Self)
Задание.
Получен целочисленный массив nums
Верните массив answer таким образом, чтобы answer[i] был равен произведению всех элементов nums, кроме nums[i].
Произведение любого префикса или суффикса nums гарантированно укладывается в 32-разрядное целое число.
Нужно написать алгоритм, который выполняется за время O (n), операцию деления использовать нельзя.
Пример 1.
Входные данные: nums = [1,2,3,4]
Результат: [24,12,8,6]
Пример 2.
Входные данные: nums = [-1,1,0,-3,3]
Результат: [0,0,9,0,0]
Решение.
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> result;
int product = 1, len = nums.size();
// проход слева направо
// для каждого элемента вычисляются произведения, слева от него
for(int i = 0; i < len; i++){
result.push_back(product);
product *= nums[i];
}
// проход справа налево
// к найденным произведениям добавляются произведения справа от элемента
product = 1;
for(int i = len-1; i >= 0; i--) {
result[i] *= product;
product *= nums[i];
}
return result;
}
};