Вопрос интервью: три массива и O (N * N)

Question

Предположим, у нас есть три массива длины N , которые содержат произвольные числа типа long.Тогда нам дают число M (того же типа), и наша миссия состоит в том, чтобы выбрать три числа A , B и C по одному от каждого массива (другими словами A следует выбирается из первого массива, B из второго и C из третьего), поэтому сумма A + B + C = M .

Вопрос: Можем ли мы выбрать все три числа и получить временную сложность O (N ² ) ?

---

Иллюстрация:

Массивы:

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

И M нам дали 19 .Тогда наш выбор будет 8 от первого, 4 от второго и 7 от третьего.

Answer 1

Это можно сделать в O (1) пространстве и O (N ² ) времени.

Сначала давайте решим более простую задачу:
Учитывая два массива A и B, выбираем по одному элементу из каждого, чтобы их сумма равнялась данному числу K.

Сортировка обоих массивов, которая занимает O (NlogN).
Возьмите указатели i и j, чтобы i указывал на начало массива A, а j указывал на конец B.
Найдите сумму A[i] + B[j] и сравните ее с K

• если A[i] + B[j] == K мы нашли пара A[i] и B[j]
• если A[i] + B[j] < K, нам нужно увеличить сумму, поэтому приращение i.
• если A[i] + B[j] > K, нам нужно уменьшить сумму, чтобы уменьшить j.

Этот процесс поиска пары после сортировки занимает O (N).

Теперь давайте возьмем исходную задачу. У нас есть третий массив, теперь назовите его C.

Итак, алгоритм теперь такой:

foreach element x in C
  find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x
end for

Внешний цикл запускается N раз, и для каждого запуска мы выполняем операцию O (N), делая весь алгоритм O (N ² ).

Answer 2

Вы можете свести ее к аналогичной проблеме с двумя массивами, которые довольно популярны и имеют простое решение O (n) (включая итерации с обоих концов).

1. Сортировка всех массивов.
2. Попробуйте каждое число A из первого массива один раз.
3. Найдите, могут ли последние два массива дать нам числа B и C, например B + C = M - A.

Умноженные шаги 2 и 3 дают нам O (n ^ 2) сложность.

Answer 3

Другие решения уже лучше, но в любом случае вот мое решение O (n ^ 2) времени и памяти O (n).

Вставьте все элементы массива C в хеш-таблицу.(временная сложность O (n), пространство O (n)). Возьмем все пары (a, b), a из A и b из B (временная сложность O (n ^ 2)).Для каждой пары проверьте, существует ли M- (a + b) в таблице hastable (ожидаемая сложность O (1) для каждого запроса).

Итак, общая сложность времени равна O (n ^ 2), иПространственная сложность O (n) для хеш-таблицы.

Answer 4

1.Сохранить A [i] * B [j] для всех пар (i, j) в другом массиве D, организованном в хэш-структуре данных. Сложность этого шага O (N * N).

construct a hash named D
for i = 1 to n
    for j = 1 to n
        insert A[i]*B[j] into D

2. Для каждого C [i] в ​​массиве C найдите, существует ли M-C [i] в ​​D. Сложность этого шага O (N).

for i = 1 to n
    check if M - C[i] is in D

Answer 5

У меня есть решение.Вставьте все элементы из одного списка в хэш-таблицу.Это не займет O (n) времени.

Как только это будет завершено, вы найдете все пары из оставшихся 2 массивов и посмотрите, присутствует ли их сумма в хеш-таблице.

Потому что хешподключение постоянное, мы получаем общее квадратичное время.

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

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

Answer 6

Хэш последнего списка. Время, необходимое для этого, составляет O (N) в этом конкретном списке, но это будет добавлено к следующему этапу.

Следующим этапом является создание «матрицы» из первых двух строк их сумм. Затем посмотрите в хэше, есть ли соответствующий номер. Создание матрицы - это O (N * N), а поиск в хэше - это постоянное время.

Answer 7

Сортировка трех массивов. Затем инициализируйте три индекса

1. i, указывающих на первый элемент A,
2. j, указывающих на последний элемент B и

3. k указывает на первый элемент C. В то время как i, j, k находятся в пределах своих соответствующих массивов A, B, C

4. Если A [i] + B [j] + C [k] == M вернуть

5. Если A [i] + B [j] + C [k]

6. Если A [i] + B [j] + C [k]> M. Уменьшение j.

Который должен работать вО (п). * * 1 023

Answer 8

У меня есть другое O(N^2) временное усложнение, O(N) дополнительное решение для усложнения пространства.

Сначала отсортируйте три массива, этот шаг равен O(N*log(N)).Затем для каждого элемента в A создайте два массива V = Ai + B и W = Ai + C (Ai - текущий элемент).Ai + B означает, что каждый элемент этого нового массива V является элементом в этой позиции в B плюс Ai (текущий элемент в A).W = Ai + C аналогично.

Теперь объедините V и W, как в сортировке слиянием.Поскольку оба отсортированы, это O(N).В этом новом массиве с 2*N элементами ищите M + Ai (потому что Ai используется дважды).Это можно сделать в O(log n) с помощью бинарного поиска.

Следовательно, общая сложность составляет O(N^2).

Answer 9

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

Хеш-таблица также является жизнеспособным вариантом.

Комбинация хэша и сортировки может сократить время, но за счет O (N квадрат) пространства.

Answer 10

Ценой пространства O (N ^ 2), но продолжая использовать время O (N ^ 2), можно обрабатывать четыре массива, вычисляя все возможные суммы из первых двух массивов, и По всем возможным остаткам из последних двух отсортируйте списки (возможно за линейное время, поскольку все они имеют тип «long», число битов которого не зависит от N), а затем проследите, равна ли любая сумма какому-либо остатку.