Произведение элементов массива кроме текущего
Дан целочисленный массив nums. Верните массив output, где output[i] равен произведению всех элементов массива nums, кроме nums[i].
Произведение любого префикса или суффикса nums гарантированно помещается в 32-битное целое число.
Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления.
Пример 1:
Input: nums = [1, 2, 4, 6] Output: [48, 24, 12, 8]
Пример 2:
Input: nums = [-1, 0, 1, 2, 3] Output: [0, -6, 0, 0, 0]
Рекомендуемая временная и пространственная сложность
Вам следует стремиться к решению с временной сложностью O(n) и пространственной сложностью O(1) (не считая выходной массив), где n — размер входного массива.
Подсказка 1
Вместо деления произведения всех чисел на каждое число, можете ли вы построить ответ, рассматривая произведения с обеих сторон?
Подсказка 2
Подумайте о вычислении префиксных произведений (произведений всех чисел слева) и суффиксных произведений (произведений всех чисел справа) для каждой позиции.
Подсказка 3
Можете ли вы использовать выходной массив для хранения одного из произведений (префиксного или суффиксного), чтобы достичь O(1) дополнительного пространства?