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

Question

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

Входной сигнал: два отсортированных массива целых чисел А и В, каждый из длины п

Выход: Один отсортированного массива, который состоит из декартово произведение массивов А и В.

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 (п ² журнала п) он должен сделать больше, чем просто использовать тот факт, что А и В уже отсортирован. См. Мой ответ this question.

---

Srikanth задается вопросом, как это может быть сделано в O (п) пространство (не считая места для выхода). Это можно сделать, создавая списки лениво.

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

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

Найти наименьший элемент этого списка (6 × 3), выводить его, заменить его с этим элементом в раз следующий элемент в 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), если мы сохраним этот список в heap.

Answer 2

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

А 1, 3, 5

В является 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.

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

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