Этот пост посвящен очень красивому вопросу из интервью, который однажды задал 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) для заполнения массива продуктов. Это все для этого поста.
Надеюсь, вам понравился пост.
Если вы сочтете это полезным, поделитесь, пожалуйста, аплодисменты, безусловно, приветствуются! ☺
А теперь тизер, а что, если вы не можете использовать разделение? Что ж, скоро напишу пост о том же. А пока не стесняйтесь комментировать, если у вас есть какие-либо вопросы.