Product of Array Except Self

Q: Почему деление не допускается в задаче «Произведение массива без текущего элемента»?

Деление произведения всех элементов на nums[i] не работает, если в массиве есть ноль: произведение равно 0, а для индекса самого нуля потребовалось бы деление на 0. Чтобы это работало, нужно подсчитывать нули и обрабатывать особые случаи. Это правило подводит к использованию префиксных и суффиксных произведений, которые обрабатывают нули без каких-либо особых случаев.

СреднеПрефиксные суммы

+10

Дан массив целых чисел nums. Верните массив answer той же длины, где answer[i] — произведение всех элементов массива nums, кроме элемента с индексом i. Выполните это за время O(n) и без использования деления.

Функция

productExceptSelf(nums: integer-array) → integer-array

numsinteger-array: массив целых чисел, содержащий не менее двух элементов
Возвращаетinteger-array: массив, значение которого по индексу i равно произведению всех элементов, кроме nums[i]

Ограничения

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
Произведение всех ненулевых значений в nums помещается в 32-разрядное целое число со знаком, поэтому любое промежуточное произведение тоже помещается.

Примеры

Ввод: nums = [2, 3, 4, 5]
Вывод: [60, 40, 30, 24]
Пояснение: Если пропустить 2, получится 3 × 4 × 5 = 60, а если пропустить 5 — 2 × 3 × 4 = 24. Для двух средних чисел всё работает так же: 2 × 4 × 5 = 40 и 2 × 3 × 5 = 30.

+14 скрытых тестов при отправке

Дополнительный вопрос

Можешь использовать только дополнительную память O(1), не считая возвращаемого массива?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Произведение всех значений, кроме nums[i], — это произведение значений слева, умноженное на произведение значений справа. Деление общего произведения на nums[i] выглядит короче, но здесь оно запрещено и не работает при наличии нулей, когда общее произведение равно 0. Префиксные и суффиксные произведения позволяют получить все произведения слева и справа за два прохода, поэтому решение работает за O(n) времени. В выходном массиве можно хранить произведения слева, а одну переменную использовать для произведения справа, поэтому другой массив не нужен.

Перемножьте остальные значения для каждого индекса

Верно, но не успевает на самых больших тестах

Идея

Следуй определению. Для каждого индекса i начни произведение с 1 и умножь на каждое значение nums[j], индекс j которого не равен i. Пропуск этого индекса, а не деление на него позже, позволяет не беспокоиться о нулях: в [-2, 5, 0, 3] при вычислении произведения для индекса 2 значение 0 не учитывается, и результат равен -30.

Это правильно, но приводит к повторению вычислений. Произведения для индексов 0 и 1 содержат все значения, кроме двух, однако ты всё равно заново умножаешь их все. Для каждой из n позиций требуется n-1 умножений — всего около 10^8 при n = 10^4. C справляется с этим за доли секунды, но Python, Ruby или R работают слишком долго.

Алгоритм

Создай массив ответов длины n.
Для каждого индекса i установи значение product равным 1.
Умножь product на каждый nums[j], индекс j которого не равен i.
Сохрани product по индексу i в массиве ответов.
Верни массив ответов.

def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

Массивы произведений префиксов и суффиксов

Идея

Раздели произведение для индекса i на две части: значения перед i и значения после него. Назови эти произведения before[i] и after[i]. Тогда answer[i] = before[i] × after[i], а nums[i] пропускается без какого-либо деления.

Каждый массив растёт от соседнего элемента с помощью одного умножения. before[0] равно 1 — произведению, не содержащему ни одного значения, а before[i] = before[i-1] × nums[i-1]. С другого конца after[n-1] равно 1, а after[i] = after[i+1] × nums[i+1]. Для [2, 3, 4, 5] получаются before = [1, 2, 6, 24] и after = [60, 20, 5, 1], а их поэлементное умножение даёт [60, 40, 30, 24].

Три прохода по n шагов дают время O(n). Два вспомогательных массива требуют O(n) дополнительной памяти, от которой позволяет избавиться следующий подход.

Алгоритм

Заполни before слева: before[0] = 1, затем каждое значение равно предыдущему значению, умноженному на предыдущее число.
Заполни after справа: after[n-1] = 1, затем каждое значение равно следующему значению, умноженному на следующее число.
Для каждого индекса установи answer[i] равным before[i] × after[i].
Верни answer.

def productExceptSelf(nums):
    n = len(nums)
    # before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
    before = [1] * n
    after = [1] * n
    for i in range(1, n):
        before[i] = before[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1] * nums[i + 1]
    return [before[i] * after[i] for i in range(n)]

Слева произведения в ответе, справа — одно текущее произведение

Идея

Тебе никогда не нужен весь массив after сразу. Если двигаться от правого конца, произведение значений справа от i — это одно число. Храни его в переменной right и обновляй одним умножением на каждом шаге.

Поэтому на первом проходе записывай произведения слева прямо в массив ответа. На втором проходе справа налево умножай answer[i] на right и только после этого умножай right на nums[i]. Порядок важен: когда ты используешь right на индексе i, он пока не должен включать nums[i].

Для [2, 3, 4, 5] после первого прохода получится [1, 2, 6, 24]. На втором проходе значения right равны 1, 5, 20, 60 на индексах 3, 2, 1, 0, и массив превращается в [60, 40, 30, 24]. Время работы по-прежнему составляет O(n), а помимо возвращаемого массива дополнительная память — одна переменная: O(1).

Алгоритм

Задай answer[0] = 1, затем слева направо задай answer[i] = answer[i-1] × nums[i-1].
Задай right равным 1.
Начиная с последнего индекса и двигаясь до 0, умножай answer[i] на right.
Затем умножай right на nums[i].
Верни answer.

def productExceptSelf(nums):
    n = len(nums)
    # Pass 1: answer[i] = product of everything left of i
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    # Pass 2: multiply in the product of everything right of i
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

Ловушки и крайние случаи

Ошибки здесь связаны с нулями, порядком двух обновлений во втором проходе и границами массива.

Деление общего произведения на nums[i] перестаёт работать, как только появляется 0. Для [-2, 5, 0, 3] общее произведение равно 0, и для индекса 2 потребуется разделить 0 на 0. Можно учесть количество нулей, но по условию задачи деление всё равно запрещено.
Если умножить right на nums[i] до того, как использовать его, nums[i] попадёт в собственное произведение. Для [2, 3, 4, 5] последнее значение станет равным 120 вместо 24.
Начало вычисления произведений слева с nums[0] вместо 1. Слева от индекса 0 ничего нет, поэтому произведение пустого набора равно 1, и answer[0] в итоге будет произведением только значений справа от него.
Границы циклов: левый проход читает nums[i-1], поэтому он начинается с индекса 1. Суффиксный массив читает nums[i+1], поэтому он начинается с индекса n-2.
При двух нулях каждый ответ равен 0. При одном нуле каждый ответ равен 0, кроме ответа на месте самого нуля. Проверь оба случая, прежде чем доверять своему коду.

Частые вопросы4

Какова временная сложность алгоритма «Произведение всех элементов массива, кроме текущего»?

Решение с префиксами и суффиксами работает за время O(n): один проход слева направо и один справа налево. Если произведения слева хранятся в выходном массиве, а для произведений справа используется одна переменная, оно требует O(1) дополнительной памяти, помимо выходного массива. Умножение всех остальных значений для каждого индекса занимает O(n²) времени.

Почему деление не допускается в задаче «Произведение массива без текущего элемента»?

Деление произведения всех элементов на nums[i] не работает, если в массиве есть ноль: произведение равно 0, а для индекса самого нуля потребовалось бы деление на 0. Чтобы это работало, нужно подсчитывать нули и обрабатывать особые случаи. Это правило подводит к использованию префиксных и суффиксных произведений, которые обрабатывают нули без каких-либо особых случаев.

Считается ли выходной массив дополнительной памятью?

Нет. В любом случае нужно вернуть результат, поэтому по принятому соглашению он не учитывается при подсчёте памяти. Следовательно, хранение в нём произведений слева и хранение произведения справа в одной переменной считается дополнительной памятью O(1).

Как Product of Array Except Self обрабатывает нули?

При использовании произведений префиксов и суффиксов нули не требуют отдельной обработки. Любое произведение слева или справа, которое включает ноль, равно 0, а произведение для индекса самого нуля пропускает его. Если нулей два или больше, каждое произведение содержит ноль, поэтому каждый ответ равен 0.

Python

def productExceptSelf(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [2, 3, 4, 5]

Ожидается

[60, 40, 30, 24]

Product of Array Except Self

Функция

Ограничения

Примеры

Подсказки

Решение

Перемножьте остальные значения для каждого индекса

Массивы произведений префиксов и суффиксов

Слева произведения в ответе, справа — одно текущее произведение

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи