Вот и у меня вторая проблема !.

Проблема

Учитывая массив целых чисел, верните новый массив так, чтобы каждый элемент в индексе 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)

Надеюсь, вам понравился этот пост.

Если вы сочтете это полезным, поделитесь, и мы будем благодарны за аплодисменты! 😄

Не стесняйтесь задавать свои вопросы в разделе комментариев !.