Итак, для начала я сделал несколько предположений о конце большего массива: пространство в конце заполнено значениями -1. Я думаю, вы можете выбрать любое значение, но это то значение, которое мне показалось разумным.
Наивное решение этой проблемы состоит в том, чтобы просто создать новый массив размером с большой массив и выбрать один из двух массивов по мере итерации, чтобы заполнить новый массив в отсортированном порядке. Это будет выполняться за линейное время, но потребует O(n) дополнительного пространства (где n — размер большего массива).
Если пространство является проблемой, следующее решение выполняется в пространстве O (1):
Это решение просто заменяет максимальное значение любого массива следующей позицией в буфере. Эффект заключается в том, что вы получаете своего рода «скользящее окно», которое сжимается, когда вы заменяете элементы из меньшего массива:
ar1 = 1 5 9 10 15 20 -1 -1 -1 -1 ar2 = 2 3 8 13 ar1 = 1 5 9 10 15 -1 -1 -1 -1 20 ar2 = 2 3 8 13 ar1 = 1 5 9 10 -1 -1 -1 -1 15 20 ar2 = 2 3 8 13 ar1 = 1 5 9 10 -1 -1 -1 13 15 20 ar2 = 2 3 8 -1 ar1 = 1 5 9 -1 -1 -1 10 13 15 20 ar2 = 2 3 8 -1 ar1 = 1 5 -1 -1 -1 9 10 13 15 20 ar2 = 2 3 8 -1 ar1 = 1 5 -1 -1 8 9 10 13 15 20 ar2 = 2 3 -1 -1 ar1 = 1 -1 -1 5 8 9 10 13 15 20 ar2 = 2 3 -1 -1 ar1 = 1 -1 3 5 8 9 10 13 15 20 ar2 = 2 -1 -1 -1 ar1 = 1 2 3 5 8 9 10 13 15 20 ar2 = -1 -1 -1 -1
