Постановка задачи
Дан целочисленный массив nums, вернуть массив answer, такой, что answer [i] равен произведению всех элементов nums кроме nums [i].
Произведение любого префикса или суффикса чисел гарантированно соответствует 32-битному целому числу.
Вы должны написать алгоритм, который работает за O (n) время и без использования операции деления.
Описание проблемы взято из: https://leetcode.com/problems/product-of-array-except-self
Пример 1:
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Пример 2:
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Ограничения:
- 2 <= nums.length <= 10^5 -
-30 <= nums[i] <= 30
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Последующие действия: Сможете ли вы решить проблему за счет O (1) лишнего пространства? (Выходной массив не считается дополнительным пространством для анализа сложности пространства.)
Объяснение
Подход грубой силы
Согласно постановке задачи, мы не можем использовать оператор деления. Первый подход, который мы можем придумать, - использовать два вложенных цикла for и умножать два числа, когда индексы не совпадают.
Небольшой фрагмент приведенного выше решения на C ++ будет выглядеть, как показано ниже:
vector<int> answer(nums.size(), 0);
for(int i = 0; i < nums.size(); i++){
product = 1;
for(int j = 0; j < nums.size(); j++){
if(i != j){
product *= nums[j];
}
}
answer[i] = product;
}
Проблема с вышеупомянутым подходом - временная сложность. Временная сложность описанного выше подхода составляет O (N²).
Линейный подход
Мы можем оптимизировать приведенное выше решение до O (N), оценивая произведения элемента слева направо и справа налево.
Давайте проверим алгоритм
- initialize vector<int>answer, i
- set product = 1
- loop for i = 0; i < nums.size(); i++
- append answer.push_back(product)
- set product = product * nums[i]
- reset product = 1
- loop for i = nums.size() - 1; i >= 0; i--
- set answer[i] = answer[i]*product
- product *= nums[i]
- return answer
Решение C ++
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> answer;
int product = 1, i;
for(i = 0; i < nums.size(); i++){
answer.push_back(product);
product *= nums[i];
}
product = 1;
for(i = nums.size() - 1; i >= 0; i--){
answer[i] *= product;
product *= nums[i];
}
return answer;
}
};
Решение Голанга
func productExceptSelf(nums []int) []int {
answer := make([]int, len(nums))
product := 1
for i := 0; i < len(nums); i++ {
answer[i] = product
product *= nums[i]
}
product = 1
for i := len(nums) - 1; i >= 0; i-- {
answer[i] *= product
product *= nums[i]
}
return answer
}
Решение Javascript
var productExceptSelf = function(nums) {
var answer = [];
let product = 1;
for(let i = 0; i < nums.length; i++){
answer[i] = product;
product *= nums[i];
}
product = 1;
for(let i = nums.length - 1; i >= 0; i--){
answer[i] *= product;
product *= nums[i];
}
return answer;
};
Давайте проверим наш алгоритм, чтобы увидеть, как работает решение.
Input: nums = [1, 2, 3, 4]
Step 1: vector<int> answer
int product = 1, i
Step 2: loop for i = 0; i < nums.size()
0 < 4
true
answer.push_back(product)
answer.push_back(1)
answer = [1]
product *= nums[i]
product = product * nums[0]
= 1 * 1
= 1
i++
i = 1
Step 3: loop for i < nums.size()
1 < 4
true
answer.push_back(product)
answer.push_back(1)
answer = [1, 1]
product *= nums[i]
product = product * nums[1]
= 1 * 2
= 2
i++
i = 2
Step 4: loop for i < nums.size()
2 < 4
true
answer.push_back(product)
answer.push_back(2)
answer = [1, 1, 2]
product *= nums[i]
product = product * nums[2]
= 2 * 3
= 6
i++
i = 3
Step 5: loop for i < nums.size()
3 < 4
true
answer.push_back(product)
answer.push_back(6)
answer = [1, 1, 2, 6]
product *= nums[i]
product = product * nums[3]
= 6 * 4
= 24
i++
i = 4
Step 6: loop for i < nums.size()
4 < 4
false
Step 7: product = 1
Step 8: loop for i = nums.size() - 1; i >= 0
i = 4 - 1 = 3
i >= 0
3 >= 0
true
answer[i] *= product
= answer[3] * product
= 6 * 1
= 6
product *= nums[i]
= product * nums[3]
= 1 * 4
= 4
i--
i = 2
Step 9: loop for i >= 0
2 >= 0
true
answer[i] *= product
= answer[2] * product
= 2 * 4
= 8
product *= nums[i]
= product * nums[2]
= 4 * 3
= 12
i--
i = 1
Step 10: loop for i >= 0
1 >= 0
true
answer[i] *= product
= answer[1] * product
= 1 * 12
= 12
product *= nums[i]
= product * nums[1]
= 12 * 2
= 24
i--
i = 0
Step 11: loop for i >= 0
0 >= 0
true
answer[i] *= product
= answer[0] * product
= 1 * 24
= 24
product *= nums[i]
= product * nums[0]
= 24 * 1
= 24
i--
i = -1
Step 12: loop for i >= 0
-1 >= 0
false
Step 13: return answer
So the answer is [24, 12, 8, 6]
Первоначально опубликовано на https://alkeshghorpade.me.