Блог

В настоящее время я работаю над практическими вопросами для интервью. Прилагается скриншот вопроса, над которым я работаю ниже

Я попытался использовать подход грубой силы с использованием вложенных циклов с целью рефакторинга вложенного цикла, но он по-прежнему не прошел тесты в подходе грубой силы.

Вот код, который я пробовал:

 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
  

Мне интересно как решение методом перебора, так и более эффективное решение без использования вложенных циклов.

Линейный алгоритм, использующий кумулятивные произведения с правой стороны и с левой стороны

 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]
  

Если вам разрешено использовать импорт и действительно уродливые представления списка, вы могли бы попробовать это:

 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)]
  

Я оставляю это в качестве упражнения для читателя, чтобы поместить два решения в функцию.

Если вы хотите получить индекс каждого элемента в списке, вы должны попробовать 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
  

Я придумал это:

 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 вы создаете список списков, в каждом из которых удаляется соответствующее целое число. Затем вы просто создаете новый список с произведениями этих подсписков.

Вот решение, использующее рекурсивную функцию вместо цикла:

 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]
  

Предположим, что 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. Список индексов вне диапазона

     for i in int_list
     

   Это уже дает вам i , который является элементом списка, а не индексом. Когда i равно 7,

    int_list[i]
     

   больше невозможно.

   Циклы должны быть for ... in range(len(int_list)) .

2. С этим исправлением результат содержит слишком много элементов. В результате получается 12 элементов, но ожидается только 4. Это из-за другой проблемы с отступом в products.append(...) . Его нужно превзойти на 2 шага.

3. С этим фиксированным значением большинство 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))