Вот и у меня вторая проблема !.
Проблема
Учитывая массив целых чисел, верните новый массив так, чтобы каждый элемент в индексе
i
нового массива был произведением всех чисел в исходном массиве, кроме одного вi
.
Например, если наш ввод был
[1, 2, 3, 4, 5]
, ожидаемый результат был бы[120, 60, 40, 30, 24]
. Если бы наш ввод был[3, 2, 1]
, ожидаемый результат был бы[2, 3, 6]
.
Продолжение: что делать, если вы не можете использовать разделение?
Не стоит сразу думать об оптимальном решении.
Первое и наиболее очевидное решение - это метод грубой силы. Мы можем использовать два цикла и вычислить произведение с условием, что индексы не совпадают.
Решение 1. Использование двух петель
Python:
Go:
Сложность времени: O (n²)
Сложность пространства: O (1)
Вышеупомянутую проблему можно оптимизировать для выполнения за один проход. Вы можете его идентифицировать? Да, мы можем сделать это, в первую очередь вычислив продукт и разделив весь продукт на элемент в текущей позиции. Это даст продукт всех элементов, кроме этого элемента. Это было не так уж и сложно. Давайте реализуем это.
Решение 2.Первый расчет продукта
Python:
Go:
Сложность времени: O (n)
Сложность пространства: O (1)
Теперь нам удалось найти решение за один проход. А теперь попробуем бонусный раздел. Последующие действия говорят нам, что решение можно найти без использования метода деления. Хммм. Итак, если деление запрещено, единственное, что мы можем сделать, - это умножение. Как мы можем найти произведение всех элементов, кроме любого одного элемента ?. Не торопитесь и подумайте об этом !.
Чтобы избежать включения этого элемента и нахождения продукта других, мы можем вычислить произведение всех элементов справа и слева.
Например, если мы попытаемся найти произведение всех элементов, кроме элемента в позиции 2, мы вычислим произведение всех чисел слева от него (1 * 2) и произведение всех чисел справа от него (4 * 5 ). Таким образом, мы можем решить без деления. Как этого добиться за один проход ?. Мы можем управлять двумя массивами: один для хранения произведения всех элементов слева для каждого элемента, а другой - для хранения произведения всех элементов справа. Сначала попробуйте это сами.
Python:
Go:
Сложность времени: O (n)
Сложность пространства: O (n)
Одна из проблем с вышеупомянутым решением заключается в том, что мы используем дополнительные места для хранения произведения левых и правых элементов. Можем ли мы добиться этого, не занимая лишнего места ?. Вместо использования этих дополнительных пробелов мы можем обновить его в самом массиве результатов. Этот подход, при котором мы находим решение, вычисляя произведение элементов слева и справа, является жадным подходом.
Решение 3: жадный подход
Python:
Go:
Сложность времени: O (n)
Сложность пространства: O (1)
Надеюсь, вам понравился этот пост.
Если вы сочтете это полезным, поделитесь, и мы будем благодарны за аплодисменты! 😄
Не стесняйтесь задавать свои вопросы в разделе комментариев !.