Этот пост посвящен очень красивому вопросу из интервью, который однажды задал Uber. Формулировка вопроса следующая:

Учитывая массив целых чисел, верните новый массив, так что каждый элемент в индексе i нового массива является произведением всех чисел в исходном массиве, кроме одного в i.

Например, если наш вход был [1, 2, 3, 4, 5], ожидаемый результат был бы [120, 60, 40, 30, 24]. Если бы наш ввод был [3, 2, 1], ожидаемый результат был бы [2, 3, 6].

Самый простой подход, который может придумать кто-то, - это для любого элемента массива с индексом i взять произведение всех других элементов массива, исключая текущий индекс, и сохранить продукт для текущего индекса, то есть индекса i в массиве продуктов с его индексом i. .

Это очень простой и наивный подход, который приведет к большой временной сложности, поскольку мы должны пройти по массиву n раз для его заполнения, а затем для каждого элемента снова пройти n-1 элементов для вычисления продукта. Это означает временную сложность порядка O (n) + O (n * (n-1)).

Нам нужно подумать о лучшем подходе, который может выполнить ту же задачу за меньшее время. Итак, что, если мы воспользуемся техникой умножения и деления вместе.

Звучит сложно! Мы вместе сделаем это просто. Давай сделаем это.

Предположим, у нас есть массив ненулевых целых чисел, A = [1,2,3,4], и нам нужно найти это массив продуктов, скажем, P = []. Сначала мы объявляем переменную с именем product и инициализируем ее значением 1. Теперь, заполняя массив A, мы вычисляем продукт как:

для i = от 0 до A.length () - 1:

product = product * A [i];

(с учетом индексации на основе 0)

product в нашем случае будет 1 * 2 * 3 * 4 = 24.

Теперь мы достигли последнего шага по заполнению массива товаров P. Мы инициализируем элементы массива P, перемещаясь по массиву товаров от индекса i = 0 до i = A.length () - 1 следующим образом:

P [i] = product / A [i];

Это гарантирует, что любой элемент с индексом i в P [] будет иметь произведение оставшихся элементов, кроме самого элемента. Наше P становится, [24,12,8,6].

Мы все? Для некоторых людей мы могли бы закончить. Но на самом деле это не так! Итак, что у нас осталось?

Если присмотреться, мы рассмотрели только случай, когда массив имеет ненулевые значения. Что, если в массиве тоже есть нулевые значения? Что ж, для этого не нужно сильно беспокоиться. Я покажу тебе! Используя небольшую хитрость в описанной выше технике, мы можем справиться с нулевым случаем.

Рассмотрим массив, A = [1,2,0,5]

Выходной массив продуктов должен быть P = [0,0,10,0]. Но с помощью приведенного выше кода мы определенно не сможем этого добиться. Нам необходимо внести следующие изменения:

Во время обхода массива A в первый раз нам нужно учитывать три вещи:

  • Ненулевой продукт (продукт)
  • Если есть нулевой элемент (isZero)
  • Количество нулей (numZeros)

Ненулевой продукт - это произведение всех Ai, которые не равны нулю.

Если при обходе A мы находим нулевой элемент, то устанавливаем логический флаг true для переменной ifZero.

Подсчитайте количество нулей в A и сохраните его в переменной numZeros.

Теперь, когда мы закончили с этим, нам нужно заполнить наш массив товаров, то есть P.

Для этого мы сначала проверяем, не превышает ли numZeros значение 1.

  • Если numZeros больше 1, это означает, что исходный массив имеет как минимум два нуля, и, следовательно, массив продуктов будет содержать все нули, и все готово. A = [1,2,0,0], поэтому P = [0,0,0,0]
  • Если numZeros меньше или равно 1, это означает, что исходный массив A должен иметь либо один ноль, либо не иметь нуля. Если isZero ложно, это становится случаем, когда все ненулевые значения в массиве могут быть легко решены (подход, который мы обсуждали в сообщении выше). Но если isZero истинно, это означает, что в массиве один элемент равен нулю. Тогда в этом случае, чтобы заполнить массив продуктов P, мы должны проявлять особую осторожность, когда A [i] равно нулю. Это несложно, и мы легко справимся с этим. Мы можем просто заполнить массив товаров следующим образом:

If(A[i]) P[i]=0;

else P [i] = product;

Здесь, если текущий элемент не равен нулю, то его аналог продукта должен быть равен нулю. Если текущий элемент равен нулю, его аналог продукта должен быть ненулевым.

И вот, наконец, все готово! Таким образом, мы снизили временную сложность до O (n) + O (n). O (n) для обхода массива A в первый раз и O (n) для заполнения массива продуктов. Это все для этого поста.

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

Если вы сочтете это полезным, поделитесь, пожалуйста, аплодисменты, безусловно, приветствуются! ☺

А теперь тизер, а что, если вы не можете использовать разделение? Что ж, скоро напишу пост о том же. А пока не стесняйтесь комментировать, если у вас есть какие-либо вопросы.