В вашем коде я вижу три недостатка:
много раз вычисляется product
, что делает ваше решение квадратичным по сложности, а можно уложиться в линейное время;
int(... / ...)
теряет точность, переводя целые (которые в Питоне не ограничены) в вещественные (у которых 53 бита точности). Вот пример:
[9007199254740993, 9007199254740991] -> [9007199254740991, 9007199254740992]
- неправильно обрабатываются нули в списке.
Возможное решение всех этих проблем ниже.
Код из вопроса int(... / ...)
позволяет предположить что в списке только целые.
Наивное решение которое использует свежий Питон (3.8 и выше):
def naive_partial_products(a):
# если Питон не свежий, то вычислите произведение так
# p = functools.reduce(operator.mul, a, 1)
p = math.prod(a)
return [p // v for v in a]
Это короткое быстрое решение, которое хорошо работает пока в массиве нет нулей. Если нули есть, надо разбирать случаи. Если ноль один, то в ответе все нули кроме одного элемента. Если нулей больше одного, то в ответе одни нули.
Кроме нулей надо внимательно проследить как обрабатываются короткие массивы.
После учёта всех возможностей получается такой симпатичный монстрик:
import math
def partial_products(a):
zc = a.count(0)
if zc > 1:
return [0] * len(a)
p = math.prod(v for v in a if v != 0)
if zc == 0:
return [p // v for v in a]
return [p if v == 0 else 0 for v in a]
def check(a):
print(f'{a} -> {partial_products(a)}')
check([])
check([0])
check([0, 0])
check([0, 0, 0])
check([10])
check([0, 10])
check([1, 2, 3, 4])
check([0, 1, 2, 3, 4])
check([0, 0, 1, 2, 3, 4])
$ python partial-products.py
[] -> []
[0] -> [1]
[0, 0] -> [0, 0]
[0, 0, 0] -> [0, 0, 0]
[10] -> [1]
[0, 10] -> [10, 0]
[1, 2, 3, 4] -> [24, 12, 8, 6]
[0, 1, 2, 3, 4] -> [24, 0, 0, 0, 0]
[0, 0, 1, 2, 3, 4] -> [0, 0, 0, 0, 0, 0]
P.S. Предыдущее решение длинное и сложное со множеством краевых случаев. Можно сделать немного изящнее, но потребуется дополнительная линейная память.
Из списка [1, 2, 3, 4]
построим два списка с накопительными произведениями:
a = [ 1, 2, 3, 4]
lr = [ 1, 1, 2, 6] # lr[i] = prod(a[ :i])
rl = [24, 12, 4, 1] # rl[i] = prod(a[i + 1: ])
Список lr
строится за линейное время проходом по a
слева направо.
Список rl
строится за линейное время проходом по a
справа налево. Его потом придётся перевернуть. Поэлементное произведение lr
и rl
- ответ.
Код:
def cum_prod(seq):
p = 1
for v in seq:
yield p
p *= v
def partial_products(a):
lr = cum_prod(a)
rl = reversed(tuple(cum_prod(reversed(a))))
return [a * b for a, b in zip(lr, rl)]
product
(линейная сложность -> квадратичная сложность;int(... / ...)
теряет точность, лучше... // ...
; неправильно обрабатываются нули в списке.