эффективное отсортированное декартово произведение двух отсортированных массивов целых чисел

Question

Нужно Подсказки для разработки эффективного алгоритма, который принимает следующие входные данные и выдает следующий вывод.

Входные данные: два отсортированных массива целых чисел A и B, каждая из которых имеет длину n

Вывод: один отсортированный массив, состоящий из декартовых произведений массивов A и B.

For Example: 

Input:
A is 1, 3, 5
B is 4, 8, 10
here n is 3.

Output:
4, 8, 10, 12, 20, 24, 30, 40, 50

Вот мои попытки решить эту проблему.

1) Учитывая, что выводравно n ^ 2, эффективный алгоритм не может быть лучше, чем сложность времени O (n ^ 2).

2) Сначала я попробовал простой, но неэффективный подход.Генерация декартовых произведений A и B. Это можно сделать за O (n ^ 2) временных сложностей.нам нужно хранить, чтобы мы могли сделать сортировку по нему.Поэтому O (n ^ 2) пространственная сложность тоже.Теперь мы сортируем n ^ 2 элементов, которые нельзя сделать лучше, чем O (n ^ 2logn), не делая никаких предположений на входе.

Наконец, у меня есть O (n ^ 2logn) времени и O (n ^2) алгоритм пространственной сложности.

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

Answer 1

Если есть решение, которое лучше, чем O ( n ² log n ), ему нужно сделать больше, чем просто использовать тот факт, что A и B уже отсортированы.Смотрите мой ответ на этот вопрос .

---

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

Предположим, у нас A = 6,7,8 и B = 3,4,5.Сначала умножьте каждый элемент в A на первый элемент в B и сохраните их в списке:

6 × 3 = 18, 7 × 3 = 21, 8 × 3 = 24

Найдите наименьший элемент этого списка (6 × 3), выведите его, замените его на этот элемент за A, умноженный на следующий элемент в B:

7 × 3 = 21, 6 × 4 = 24 , 8 × 3 = 24

Найдите новый наименьший элемент этого списка (7 × 3), выведите его и замените:

6 × 4 = 24, 8 × 3 = 24, 7 × 4 = 28

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

Answer 2

Если умножить значение A на все значения B, список результатов все равно будет отсортирован. В вашем примере:

А составляет 1, 3, 5

B = 4, 8, 10

1 * (4,8,10) = 4,8,10

3 * (4,8,10) = 12,24,30

Теперь вы можете объединить два списка (точно так же, как в сортировке слиянием). Вы просто смотрите на обе главы списка и помещаете меньшую в список результатов. так что здесь вы бы выбрали 4, затем 8, затем 10 и т. д. результат = 4,8,10,12,24,30

Теперь вы делаете то же самое для списка результатов и следующего оставшегося списка, объединяя 4,8,10,12,24,30 с 5 * (4,8,10) = 20,40,50.

Поскольку объединение наиболее эффективно, если оба списка имеют одинаковую длину, вы можете изменить эту схему, разделив А на две части, выполнить слияние рекурсивно для обеих частей и объединить оба результата.

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