Вопрос интервью по решению проблем (массивы)

Существует массив целых чисел, скажем 3,5,7,9. Вы должны создать другой массив и заполнить его таким образом, чтобы вторая позиция 0-го массива была произведением всех чисел из первого массива, исключая число на его 0-й позиции, то есть оно должно быть 5x7x9 (исключая 3), число в индексе 1 второго массива будет произведение 3x7x9 (исключая 5).

Первый ответ, который пришел мне на ум, состоял из 2 циклов, которые приведут к временной сложности O (n2). Позже я понял это:

Умножая все числа в первом массиве (3x5x7x9), и при заполнении второго массива я делю этот продукт на число в этой позиции. разделите на 3, если я заполняю 0-ю позицию, разделите на 5, если я заполняю 1-ю позицию и так далее. Это снизит сложность от O (n2) до, вероятно, O (2n).

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

Ответы

Ответ 1

Я не уверен, что вопрос о пространстве или о самом решении. Поскольку все предлагали решения, это заставляет меня думать, что они не понимают решения интервьюера, поэтому вот объяснение:

Мы поддерживаем два массива. Первое, запущенное произведение чисел исходного массива. Таким образом, элемент в месте i будет произведением первых элементов i в исходном массиве (без латекса, но запись i th имеет значение it pi{j=0 to i} j). Второй массив - это просто обратное направление, поэтому запись i th будет иметь значение: pi{j=N-i to N} j.

Чтобы построить требуемый конечный массив, мы просто запускаем каждый из наших двух массивов и умножаем записи. Таким образом, значение i th в конечном массиве будет произведением всех записей, которое является произведением от 0 до i-1 умножить произведение i+1 на N, который является произведением первой записи массива i-1 и второй записи массива i+1.

Общее время и пространство O(n)

Ответ 2

  • Храните элементы с 1 по я в массив A, с A[i]являясь произведением элемента 1 на элемент i;

  • Храните элементы i-n (размер ввода) в массив B, причем B[i] является произведением элемента я в элемент n;

  • Когда нужен результат [i], используйте A [i-1] * B [i + 1]. Угловые корпуса тривиальным образом, просто используйте B [1] и A [n-2] (при этом A [n-1] является последним элемент).

Ответ 3

Я думаю, что могу сделать это в O (n log n).

Храните продукт первой половины номеров и второй половины номеров.

Также сохраняйте продукт первого квартала, второго квартала, третьего квартала и четвертого квартала.

Также сохраните продукт первой восьмой, второй восьмой, восьмой восьмой.

И так далее.

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

Общее количество дополнительных данных здесь O (n) и принимает O (n) для вычисления (легко показать).

Теперь, чтобы вычислить результат для (скажем) элемента 0, вы берете произведение второй половины, произведение второй четверти (т.е. вторую половину первой четверти), произведение второй половины первый восьмой и т.д., и умножьте их вместе. Существует log n таких чисел, поэтому эта операция является log n.

Чтобы вычислить произведение для элемента k, напишите k в бинарном файле и переверните его биты. Высокий бит затем сообщает вам, с какой половины начать; следующий бит сообщает вам, какая половина оставшейся половины используется следующей; следующий бит говорит вам, какая половина оставшейся четверти для использования следующей; и т.д.

Таким образом, любой выходной элемент можно вычислить в log n времени. Сделайте это для каждого из n выходных элементов, и вы получите O (n log n).

[править]

Конечно, также работает подход "вперед и назад". Думаю, я должен внимательно прочитать вопрос.: -)

[edit 2]

Что касается решения интервьюера (и davin), вам фактически не нужно создавать дополнительный массив... Предполагая, что вы можете редактировать значения в выходном массиве.

Сначала построим выходной массив B такой, что B [i] = A [0] A [1]... * A [i-1] и B [0] = 1. Вы можете сделать это постепенно, поэтому это линейное время:

B[0] = 1;
for (i=1 ; i < n ; ++i) {
    B[i] = B[i-1] * A[i];
}

Затем сканирование назад с n-2 для вычисления ответов, отслеживание "продукта до сих пор":

x = A[n-1];
for (j=n-2 ; j >= 0 ; ++j) {
    B[j] *= x;
    x *= A[j];
}

Это решает проблему в O (n) без создания дополнительного массива.

Ответ 4

Я считаю, что он имел в виду, что, учитывая массив A = {a_1,..., a_n}, он создаст два новых массива:

F_A = {a_1, a_1 * a_2,..., a_1 *... * a_n}

который может быть построен в линейном времени, поддерживая кумулятивный продукт, итерации вперед по массиву, и

B_A = {a_1 *... * a_n,..., a_n * a_ (n-1), a_n}

который может быть построен в линейном времени, поддерживая кумулятивный продукт при повторении в обратном направлении по массиву.

Теперь, чтобы заполнить индекс я в массиве результатов, вы просто умножаете F_A [i-1] на B_A [i + 1]:

F_A [i-1] * B_A [i + 1] = [a_1 *... * a_ (i-1)] * [a_ (i + 1) *... * a_n]

Ответ 5

Как насчет абсурда Логарифма. Вместо деления вы вычитаете?

Но если вы можете изменить 1-й массив, вы можете сделать что-то вроде

//pop arr2
r=1
for(i=len-1;i>=0;i--)
{
   r=r*arr1[i]
   arr2[i]=r
}

//modify arr1
r=1
for(i=0;i<len;i++)
{
   r=r*arr1[i]
   arr1[i]=r
}

//fix arr2
arr2[0]=arr2[1];
for(i=1;i<len-1;i--)
{
     arr2[i]=arr2[i+1]*arr1[i-1];
}
arr2[len-1]=arr1[len-2];