Исходные данные: массив с числами типа Integer. Вам нужно написать функцию, которая на входе получит исходный массив, а на выходе вернет массив, в котором каждое значение получено путем произведения всех значений исходного массива с отличным от текущего индексом.
Для ясности приведем пример. Допустим, исходный массив имеет вид:
1 | [1, 7, 3, 4] |
Тогда функция должна вернуть:
1 | [84, 12, 28, 21] |
Расчет значений происходит следующим образом:
1 | [7*3*4, 1*3*4, 1*7*4, 1*7*3] |
Дополнительные условия:
- Нельзя использовать деление.
- Функция должна быть с наименьшими затратами памяти и времени выполнения.
Решение
Для того, чтобы вычислить возвращаемый массив без использования деления, мы дважды пройдемся по массиву. Проходя первый раз, мы будем получать произведение всех значений до текущего индекса и сохранять это произведение в отдельном массиве poducts_of_all_ints_except_at_index. В этом же массиве будем сохранять результат произведения всех значений после текущего индекса, но уже идя в обратном порядке. Ответ же мы получим, перемножив значения перед и после индекса во время обратного прохода по массиву.
Код решения (на Python):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | 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