Сложность: medium
Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i].
Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число.
Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления.
Пример:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
👨💻 Алгоритм:
1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].
2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.
3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.
😎 Решение:
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
length = len(nums)
L = [1] * length
R = [1] * length
answer = [1] * length
for i in range(1, length):
L[i] = nums[i - 1] * L[i - 1]
for i in range(length - 2, -1, -1):
R[i] = nums[i + 1] * R[i + 1]
for i in range(length):
answer[i] = L[i] * R[i]
return answer
Ставь 👍 и забирай 📚 Базу знаний