238. Product of Array Except Self

Given an array of n (n > 1) integers nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it in O(n) and costant space complexity.

For example, given [1,2,3,4], return [24,12,8,6].

238. Произведение массива кроме самого

Задан массив из n (n > 1) целых чисел nums. Вернуть массив, в котором output[i] равно произведению всех элементов из nums кроме nums[i].

Решите задачу за время O(n) и константную память.

Например, для массива [1,2,3,4] следует вернуть [24,12,8,6].

// C++

class Solution {

public:

vector<int> productExceptSelf(vector<int>& nums) {

}

};

// Java

public class Solution {

public int[] productExceptSelf(int[] nums) {

}

}

РЕШЕНИЕ

последовательности

Анализ алгоритма

Пусть prod – произведение всех чисел. Тогда output[i] = prod / nums[i]. Однако такое решение не работает, если массив nums изначально содержит нули.

Заведем два массива:

t₁[i] будет содержать произведение префикса nums[0] * … * nums[i – 1];

t₂[i] будет содержать произведение суффикса nums[i + 1] * … * nums[n – 1];

Положим t₁[0] = t₂[n – 1] = 1. Тогда output[i] = t₁[i] * t₂[i].

Реализация алгоритма

class Solution

{

public:

vector<int> productExceptSelf(vector<int>& nums) // [1,2,3,4]

{

int i, size = nums.size();

vector<int> t1(size), t2(size);

t1[0] = 1;

for(i = 0; i < size - 1; i++) // [1,1,2,6]

t1[i+1] = t1[i] * nums[i];

t2[size-1] = 1;

for(i = size - 1; i > 0; i--) // [24,12,4,1]

t2[i-1] = t2[i] * nums[i];

vector<int> res;

for(i = 0; i < size; i++) // [24,12,8,6]

res.push_back(t1[i] * t2[i]);

return res;

}

};

Java реализация

class Solution

{

public int[] productExceptSelf(int[] nums)

{

int size = nums.length;

int t1[] = new int[size];

int t2[] = new int[size];

t1[0] = 1;

for(int i = 0; i < size - 1; i++) // [1,1,2,6]

t1[i+1] = t1[i] * nums[i];

t2[size-1] = 1;

for(int i = size - 1; i > 0; i--) // [24,12,4,1]

t2[i-1] = t2[i] * nums[i];

int res[] = new int[size];

for(int i = 0; i < size; i++) // [24,12,8,6]

res[i] = t1[i] * t2[i];

return res;

}

}