Product of Array Except Self

Средняя№238с двух сторон

Дан массив целых чисел. Нужно вернуть массив, где на месте i стоит произведение всех чисел, кроме nums[i]. Делить нельзя, время — O(n). Наш пример: [2, 3, 0, 4] — ответ [0, 0, 24, 0]: только нулю достаётся 2 × 3 × 4 = 24, во все остальные произведения входит 0.

238 Product of Array Except SelfРазбор · 1×

Пример: [2, 3, 0, 4]. Под числами — answer, ниже — накопленные произведения left и right.

numsanswerleft–right–02132034
ещё не дошлитекущий индекспроизведение слевав произведении справаготовый ответ

4 числа, одно из них 0

01/29
сначала · назад · пуск · шаг
Скорость
1function productExceptSelf(nums):
2 n = len(nums)
3 answer = array of n ones
4 left = 1
5 for i from 0 to n - 1:
6 answer[i] = left
7 left = left * nums[i]
8 right = 1
9 for i from n - 1 down to 0:
10 answer[i] = answer[i] * right
11 right = right * nums[i]
12 return answer
состояние
n
4
answer
–
left
–
right
–
i
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Произведение всех чисел, кроме nums[i], — это произведение всего, что левее i, умноженное на произведение всего, что правее. Первый проход оставляет в answer[i] левую часть, второй домножает на правую.
  2. answer[i] записывается до того, как nums[i] входит в left или right, поэтому число никогда не попадает в своё произведение. Так нулю и достаётся 24.
  3. Деление здесь и так бы не сработало: произведение всех чисел равно 0, а 0 / 0 ничего не даёт. Два прохода ничего не делят, и 0 для них — обычное число.

Сложность

Время O(n): два прохода. Память O(1), не считая самого ответа: left и right — просто числа.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.