Поиск k-го наименьшего числа из n отсортированных массивов

Итак, у вас есть n отсортированных массивов (не обязательно одинаковой длины), и вы должны вернуть k-й наименьший элемент в объединенном массиве (т.е. объединенный массив, образованный путем слияния всех отсортированных массивов n)

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

После этого я попытался обобщить его на поиск k-го наименьшего из двух отсортированных массивов. Здесь - вопрос о SO. Даже здесь данное решение не очевидно для меня. Но даже если мне как-то удастся убедить себя в этом решении, мне все еще любопытно, как решить абсолютный общий случай (это мой вопрос)

Может кто-нибудь объяснить мне пошаговое решение (которое, опять же, на мой взгляд, должно логарифмически меняться, то есть O (log (n ₁) + log (n ₂))... + log (n _N), где n ₁, n ₂... n _N - это длины n массивов), которая начинается с более конкретных случаев и переходит к более общей?

Я знаю, что подобные вопросы для более конкретных случаев существуют по всему Интернету, но я не нашел убедительного и ясного ответа.

Здесь есть ссылка на вопрос (и его ответ) на SO, который посвящен 5 отсортированным массивам и нахождению медианы объединенного массива. Ответ просто становится слишком сложным для меня, чтобы его обобщить.

Приветствуются даже чистые подходы к более конкретным случаям (как я упоминал во время публикации).

PS: Считаете ли вы, что это может быть дополнительно обобщено на случай несортированных массивов?

PPS: Это не домашняя проблема, я просто готовлюсь к интервью.

Ответ 1

Это не обобщает ссылки, но решает проблему:

Пройдитесь по всем массивам, и если они имеют длину > k, укоротитесь до длины k (это глупо, но мы будем возиться с k позже, так и сделайте это в любом случае)
Определите самый большой оставшийся массив A. Если более одного, выберите один.
Выберите средний элемент M самого большого массива A.
Используйте двоичный поиск на оставшихся массивах, чтобы найти тот же самый элемент (или самый большой элемент <= M).
На основе индексов различных элементов вычислим общее число элементов &lt = M и > M. Это должно дать вам два числа: L, число <= M и G, число > M
Если k < L, обрезайте все массивы в найденных точках разделения и итерации на меньших массивах (используйте нижние половины).
Если k > L, обрезайте все массивы в найденных точках разделения и повторите их на меньших массивах (используйте верхние половины и найдите элемент (k-L).

Когда вы дойдете до точки, в которой у вас есть только один элемент для каждого массива (или 0), создайте новый массив размера n с этими данными, сортируйте и выберите k-й элемент.

Поскольку вы всегда можете удалить хотя бы половину одного массива, в N итерациях вы избавитесь от половины элементов. Это означает, что есть N логических итераций. Каждая итерация имеет порядок N log k (из-за двоичных поисков), поэтому все это N ^ 2 (log k) ^ 2. Все, конечно, наихудший случай, основанный на предположении, что вы избавляетесь от половины самого большого массива, а не других массивов. На практике я полагаю, что типичная производительность будет немного лучше, чем худший.

Ответ 2

Это невозможно сделать менее чем за O(n). Доказательство эскиза. Если бы это было так, ему пришлось бы полностью не смотреть хотя бы на один массив. Очевидно, что один массив может произвольно изменять значение элемента kth.

У меня относительно простая O(n*log(n)*log(m)), где m - длина самого длинного массива. Я уверен, что можно быть немного быстрее, но не намного быстрее.

Рассмотрим простой случай, когда у вас n массивы каждой длины 1. Очевидно, что это изоморфно нахождению k -го элемента в несортированном списке длины n. Это можно найти в O(n), см. алгоритм Median of Medians, первоначально Blum, Floyd, Pratt, Rivest и Tarjan, и нет (асимптотически) возможны более быстрые алгоритмы.

Теперь проблема заключается в том, как расширить это до более отсортированных массивов. Вот алгоритм: найдите медиану каждого массива. Сортировка списка кортежей (median,length of array/2) и сортировка по медианной. Прогуляйтесь, сохраняя сумму длин, пока не достигнете суммы, большей k. Теперь у вас есть пара медиан, так что вы знаете, что k-й элемент находится между ними. Теперь для каждой медианы мы знаем, что kth больше или меньше, поэтому мы можем выбросить половину каждого массива. Повторение. После того как массивы имеют один элемент длинный (или меньше), мы используем алгоритм выбора.

Реализация этого позволит выявить дополнительные сложности и краевые условия, но ничего не увеличивает асимптотическую сложность. Каждый шаг

Находит медианы или массивы, O(1) каждый, поэтому O(n) total
Сортирует медианы O(n log n)
Просматривает отсортированный список O(n)
Срезает массивы O(1) каждый так, O(n) total

то есть O(n) + O(n log n) + O(n) + O(n) = O(n log n). И мы должны выполнить это до тех пор, пока не будет самый длинный массив длиной 1, который примет шаги log m для всего O(n*log(n)*log(m))

Вы спрашиваете, можно ли это обобщить на случай несортированных массивов. К сожалению, ответ - нет. Рассмотрим случай, когда у нас есть только один массив, тогда лучший алгоритм должен будет сравнивать хотя бы один раз с каждым элементом в общей сложности O(m). Если бы было более быстрое решение для n несортированных массивов, мы могли бы реализовать выбор, разделив наш единственный массив на n частей. Поскольку мы только что доказали, что выбор O(m), мы застреваем.

Ответ 3

Вы можете посмотреть мой недавний ответ на соответствующий вопрос здесь. Та же идея может быть обобщена на несколько массивов вместо 2. На каждой итерации вы можете отбросить вторую половину массива с наибольшим средним элементом, если k меньше суммы средних индексов всех массивов. Альтернативно, вы можете отклонить первую половину массива с наименьшим средним элементом, если k больше суммы средних индексов всех массивов, отрегулируйте k. Продолжайте делать это до тех пор, пока у вас не будет всего один массив, уменьшенный до 0. Ответ - это k-й элемент последнего массива, который не был разделен на 0 элементов.

Анализ времени выполнения:

В каждой итерации вы избавляетесь от половины одного массива. Но чтобы определить, какой массив будет уменьшен, вы тратите время линейно на количество массивов. Предположим, что каждый массив имеет одинаковую длину, время выполнения будет cclog (n), где c - количество массивов, а n - длина каждого массива.

Ответ 4

Если значение k не настолько велико, мы можем поддерживать очередь приоритетов min. затем цикл для каждой главы отсортированного массива, чтобы получить наименьший элемент и en-queue. когда размер очереди равен k. мы получаем первое k наименьшее.

возможно, мы можем рассматривать отсортированный массив n как ведра, а затем попробовать метод сортировки в виде ведра.

Ответ 5

Это можно считать второй половиной сортировки слияния. Мы могли бы просто объединить все отсортированные списки в один список... но только сохранить k элементов в комбинированных списках из слияния для слияния. Это имеет то преимущество, что используется только пространство O (k), но что-то немного лучше, чем сложность сортировки слияния (n log n). То есть, он должен на практике работать немного быстрее, чем сортировка слияния. Выбор k-го наименьшего из окончательного объединенного списка - O (1). Это не такая уж сложная задача.

Ответ 6

Существует обобщение, которое решает проблему в O (N log k) времени, см. здесь .

Ответ 7

Пожалуйста, найдите ниже код С# для поиска k-го наименьшего элемента в Союзе двух отсортированных массивов. Сложность времени: O (logk)

public int findKthElement(int k, int[] array1, int start1, int end1, int[] array2, int start2, int end2)
    {
        // if (k>m+n) exception
        if (k == 0)
        {
            return Math.Min(array1[start1], array2[start2]);
        }
        if (start1 == end1)
        {
            return array2[k];
        }
        if (start2 == end2)
        {
            return array1[k];
        }
        int mid = k / 2;
        int sub1 = Math.Min(mid, end1 - start1);
        int sub2 = Math.Min(mid, end2 - start2);
        if (array1[start1 + sub1] < array2[start2 + sub2])
        {
            return findKthElement(k - mid, array1, start1 + sub1, end1, array2, start2, end2);
        }
        else
        {
            return findKthElement(k - mid, array1, start1, end1, array2, start2 + sub2, end2);
        }
    }