#python #algorithm #big-o
#python #алгоритм #big-o
Вопрос:
В настоящее время я работаю над практическими вопросами для интервью. Прилагается скриншот вопроса, над которым я работаю ниже
Я попытался использовать подход грубой силы с использованием вложенных циклов с целью рефакторинга вложенного цикла, но он по-прежнему не прошел тесты в подходе грубой силы.
Вот код, который я пробовал:
def get_products_of_all_ints_except_at_index(int_list):
# Make a list with the products
products = []
for i in int_list:
for j in int_list:
if(i != j):
k = int_list[i] * int_list[j]
products.append(k)
return products
Мне интересно как решение методом перебора, так и более эффективное решение без использования вложенных циклов.
Комментарии:
1. Вместо использования деления, можете ли вы использовать log, exp и вычитание? 🙂
2. Вы уверены, что это ваш отступ? Он даже не будет запущен
Ответ №1:
Линейный алгоритм, использующий кумулятивные произведения с правой стороны и с левой стороны
def productexcept(l):
n = len(l)
right = [1]*n
for i in reversed(range(n-1)):
right[i] = right[i 1] * l[i 1]
#print(right)
prod = 1
for i in range(n):
t = l[i]
l[i] = prod * right[i]
prod *= t
return l
print(productexcept([2,3,7,5]))
>> [105, 70, 30, 42]
Ответ №2:
Если вам разрешено использовать импорт и действительно уродливые представления списка, вы могли бы попробовать это:
from functools import reduce
l = [1,7,3,4]
[reduce(lambda x,y: x*y, [l[i] for i in range(len(l)) if i != k],1) for k,el in enumerate(l)]
Если вам не разрешено использовать functools, вы можете написать свою собственную функцию:
def prod(x):
prod = 1
for i in x:
prod = prod * i
return prod
l = [1,7,3,4]
[prod([l[i] for i in range(len(l)) if i != k]) for k,el in enumerate(l)]
Я оставляю это в качестве упражнения для читателя, чтобы поместить два решения в функцию.
Ответ №3:
Если вы хотите получить индекс каждого элемента в списке, вы должны попробовать for i in range(len(int_list))
. for i in int_list
фактически возвращает значения в списке, но не индекс. Таким образом, решение методом перебора должно быть:
def get_products_of_all_ints_except_at_index(int_list):
# Make a list with the products
products = []
for i in range(len(int_list)):
k = 1
for j in range(len(int_list)):
if(i != j):
k *= int_list[j]
products.append(k)
return products
Ответ №4:
Я придумал это:
def product(larg):
result = 1
for n in larg:
result *= n
return result
List = [1, 7, 3, 4]
N = len(List)
BaseList = [List[0:i] List[i 1:N] for i in range(N)]
Products = [product(a) for a in BaseList]
print(Products)
Из списка ввода List
вы создаете список списков, в каждом из которых удаляется соответствующее целое число. Затем вы просто создаете новый список с произведениями этих подсписков.
Ответ №5:
Вот решение, использующее рекурсивную функцию вместо цикла:
from functools import reduce
def get_products_of_all_ints_except_at_index(int_list, n=0, results=[]):
new_list = int_list.copy()
if n == len(int_list):
return results
new_list.pop(n)
results.append(reduce((lambda x, y: x * y), new_list))
return get_products_of_all_ints_except_at_index(int_list, n 1, results)
int_list = [1, 7, 3, 4]
print(get_products_of_all_ints_except_at_index(int_list))
# expected results [84, 12, 28, 21]
Вывод:
[84, 12, 28, 21]
Ответ №6:
Предположим, что N — это степень 2.
Грубая сила принимает N (N-2) произведений. Вы можете улучшить это, предварительно вычислив N / 2 произведения пар элементов, затем N / 4 пары пар, затем пары пар пар, пока у вас не останется одна пара. Всего требуется N-2 произведения.
Затем вы формируете все запрошенные произведения путем умножения требуемых частичных произведений дихотомическим способом. Для этого требуется умножение Lg (N)-1 на произведение, следовательно, всего умножается N (Lg (N)-1).
Это решение O (N Log N).
Иллюстрация для N = 8:
Использование 6 умножает,
a b c d e f g h
ab cd ef gh
abcd efgh
Затем с 16 умножается,
b.cd.efgh
a.cd.efgh
ab.d.efgh
ab.c.efgh
abcd.f.gh
abcd.e.gh
abcd.ef.h
abcd.ef.g
Нужные выражения могут быть получены из двоичной структуры чисел от 0 до N-1.
Комментарии:
1. Насколько я могу видеть, все другие решения до сих пор являются более или менее эффективными реализациями грубой силы.
Ответ №7:
Грубая сила
Ваш подход грубой силы не работает по нескольким причинам:
(Я предполагаю, что по крайней мере фиксированный отступ)
-
Список индексов вне диапазона
for i in int_list
Это уже дает вам
i
, который является элементом списка, а не индексом. Когдаi
равно 7,int_list[i]
больше невозможно.
Циклы должны быть
for ... in range(len(int_list))
. -
С этим исправлением результат содержит слишком много элементов. В результате получается 12 элементов, но ожидается только 4. Это из-за другой проблемы с отступом в
products.append(...)
. Его нужно превзойти на 2 шага. -
С этим фиксированным значением большинство
k
перезаписывается новым значением каждый раз, когдаi*j
вычисляется. Чтобы исправить это, начнитеk
с элемента identity для умножения, который равен 1, а затем умножьтеint_list[j]
на него.
Теперь полный код
def get_products_of_all_ints_except_at_index(int_list):
products = []
for i in range(len(int_list)):
k = 1
for j in range(len(int_list)):
if i != j:
k *= int_list[j]
products.append(k)
return products
Оптимизация
Сначала я бы предложил решение «грубой силы» в качестве ответа. Не беспокойтесь о производительности, пока нет требований к производительности. Это было бы преждевременной оптимизацией.
Решение с делением было бы:
def get_products_of_all_ints_except_at_index(int_list):
products = []
product = 1
for i in int_list:
product *= i
for i in int_list:
products.append(product//i)
return products
и, следовательно, не нуждается во вложенном цикле и имеет линейную сложность с большим временем.
Небольшой трюк с показателем степени может сэкономить вам время на деление: просто умножьте на обратное:
for i in int_list:
products.append(int(product * i ** -1))
Комментарии:
1. Обратное — это скрытое деление. Нет !