Выбор ответа Middle Префиксные суммы обновлено
Произведение всех, кроме себя
Вопрос
Нужно вернуть массив, где res[i] это произведение всех элементов кроме nums[i], без деления и за O(n). Какая идея?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Произведения слева и справа: res[i] = left[i] · right[i]. Произведение «всех кроме i» это произведение всех левее i на произведение всех правее.
Варианты ответа
- Произведения слева и справа:
res[i] = left[i] · right[i]правильный ответ - Общее произведение, затем деление на
nums[i]для каждого i - Отсортировать массив и перемножать соседние элементы
- Вложенный цикл, пропускающий индекс i на каждой итерации
Разбор
Произведение «всех кроме i» это произведение всех левее i на произведение всех правее. Два прохода: слева направо и справа налево. O(n), а суффикс можно копить в переменной, тогда доп. память O(1) кроме ответа.
- Деление запрещено условием и ломается на нулях.
- Сортировка меняет позиции.
- Вложенный цикл O(n²).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.