Исходные данные: массив с числами типа Integer. Вам нужно написать функцию, которая на входе получит исходный массив, а на выходе вернет массив, в котором каждое значение получено путем произведения всех значений исходного массива с отличным от текущего индексом.
Для ясности приведем пример. Допустим, исходный массив имеет вид:
[1, 7, 3, 4]Тогда функция должна вернуть:
[84, 12, 28, 21]Расчет значений происходит следующим образом:
[7*3*4, 1*3*4, 1*7*4, 1*7*3]Дополнительные условия:
- Нельзя использовать деление.
- Функция должна быть с наименьшими затратами памяти и времени выполнения.
Решение
Для того, чтобы вычислить возвращаемый массив без использования деления, мы дважды пройдемся по массиву. Проходя первый раз, мы будем получать произведение всех значений до текущего индекса и сохранять это произведение в отдельном массиве poducts_of_all_ints_except_at_index. В этом же массиве будем сохранять результат произведения всех значений после текущего индекса, но уже идя в обратном порядке. Ответ же мы получим, перемножив значения перед и после индекса во время обратного прохода по массиву.
Код решения (на Python):
def get_products_of_all_ints_except_at_index(int_list):
# создаем дополнительный массив с таким же размером, что и исходный.
products_of_all_ints_except_at_index = [None] * len(int_list)
# Находим произведение всех значений до текущего.
# Результат помещаем в новый массив.
product_so_far = 1
i = 0
while i < len(int_list):
products_of_all_ints_except_at_index[i] = product_so_far
product_so_far *= int_list[i]
i += 1
# Находим произведение всех значений после текущего,
# при этом двигаясь по массиву в обратную сторону.
# Параллельно вычисляем значение текущей ячейки.
product_so_far = 1
i = len(int_list) - 1
while i >= 0:
products_of_all_ints_except_at_index[i] *= product_so_far
product_so_far *= int_list[i]
i -= 1
return products_of_all_ints_except_at_indexСложность полученного алгоритма — O(n) по памяти и O(n) по времени. Свои варианты предлагайте в комментариях.
Источник: Interview Cake
