K-е наименьшее число в двух массивах, один отсортирован, другой не отсортирован

Question

Уже есть ответ для двух отсортированных массивов.Однако в моем вопросе один из массивов не отсортирован.

Предположим, X[1..n] и Y[1..m], где n < m.X отсортирован, а Y не отсортирован.Какой эффективный алгоритм поиска k-го наименьшего числа из X U Y.

MinHeap можно использовать для поиска k-го наименьшего числа в несортированном массиве.Однако здесь один из этих массивов отсортирован.Я могу думать о:

 1. Building a `MinHeap` for `Y`
 2. i = 1, j = 1
 3. x1 = extract Min from Y
 4. x2 = X[i]; 
 5. if j == k: return min(x1, x2)
 5. if x1 < x2: j++; goto 3
 6. else: j++; i++; goto 4 

Это эффективно и правильно?

Answer 1

Создайте максимальную кучу самых маленьких k элементов из отсортированного массива (X).Это занимает O (k) времени.

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

Когда вы закончите, наименьшее k-е число будет в верхней части кучи.

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

Answer 2

Там нет помощи, но вы должны сканировать Y.Это займет O(m), поэтому вы не можете сделать лучше, чем O(m).

Однако Быстрый выбор имеет среднюю производительность O(m).По сути, этот алгоритм просто выполняет быструю сортировку, за исключением того, что вы игнорируете все разделы, в которых нет вашего окончательного ответа.

Учитывая, что n < m мы можем просто соединить один массив с другим и сделать быстрый выбор.

Обратите внимание, что средняя производительность хорошая, но наихудшая производительность квадратичная.Чтобы исправить это, если вы не делаете прогресс достаточно быстро, вы можете переключиться на тот же алгоритм медианы медиан, который дает гарантированную производительность быстрой сортировки (хотя и с плохими константами).Если вы не знакомы с ним, это тот, где вы делите массив на группы по 5, находите медиану каждой группы, а затем повторяете, пока не дойдете до 1 элемента.Затем используйте этот элемент как опору для всего массива.