Номер вставки из неупорядоченного списка чисел в отсортированный список чисел

Question

У меня есть список A, который его элементы отсортированы от самых маленьких до самых больших. Например:

A = 1, 5, 9, 11, 14, 20, 46, 99

Я хочу, чтобы вставить элементы, не сортированный список номеров внутри, сохраняя при этом A отсортировано. Например:

В = 0, 77, 88, 10, 4

собирается быть вставлен в А следующим образом:

А = 0, 1, 4, 5, 9, 10, 14, 20, 46, 77, 88, 99

Какое это наилучшее возможное решение?

Answer 1

Лучшее из возможных является слишком субъективным в зависимости от определения наилучшего. С большой точки зрения, имеющей массив A длиной n1 и массив B длиной n2, вы можете достичь этого в max(n2 * log(n2), n1 + n2).

Это может быть достигнуто путем сортировки массива B в O(n log n), а затем merging two sorted arrays в O(n + m)

Answer 2

Лучшее решение зависит от того, как вы определили лучших.

Даже для временной сложности все еще зависит от вашего размера ввода A и B. Предположим, что размер входного сигнала A равен m, а размер ввода B равен n.

Как отметил Сальвадор, сортировка B в O (nlogn) и слияние с A в O (m + n) является хорошим решением. Обратите внимание, что вы можете сортировать B в O (n), если вы примете некоторый алгоритм сортировки без сравнения, например, сортировку сортировки, сортировку по методу radix и т. Д.

Я предоставляю другое решение здесь: зациклируйте все элементы в B и выполните двоичный поиск в A, чтобы найти положение вставки, а затем вставить. Сложность времени - O (nlog (m + n)).

Редактировать 1: Как указывает @moreON, двоичный поиск и затем вставляемый подход предполагают, что вы перечисляете поддержку реализации, по крайней мере, амортизированную O (1) для вставки и произвольного доступа. Также установлено, что временная сложность должна быть O (nlog (m + n)) вместо O (nlogm), поскольку бинарный поиск занимает больше времени, когда добавляется больше элементов.