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

Question

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

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

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

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

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

Answer 1

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

1. Пройдите через все массивы и, если они есть, имеют длину> k, обрежьте до длины k (это глупо, но мыпозже я буду связываться с k, так что сделайте это в любом случае)
2. Определите самый большой оставшийся массив A. Если их больше одного, выберите один.
3. Выберите средний элемент M самого большого массива A.
4. Используйте бинарный поиск по оставшимся массивам, чтобы найти тот же элемент (или самый большой элемент <= M). </li>
5. На основе индексов различных элементов вычислите общее количество элементов<= M и> M. Это должно дать вам два числа: L, число <= M и G, число> M
6. Если k
7. Если k> L, обрежьте все массивы в найденных точках разбиения и выполните итерацию по меньшим массивам (используйте верхние половины ипоиск элемента (кЛ).

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

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

Answer 2

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

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

Рассмотрим простой случай, когда у вас есть n массивы, каждый из которых имеет длину 1. Очевидно, это изоморфно нахождению k-го элемента в несортированном списке длины n. Это можно найти в O(n), см. Алгоритм медианы медиан, изначально разработанный Блюмом, Флойдом, Праттом, Ривестом и Тарьяном , и более быстрые (асимптотически) алгоритмы невозможны.

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

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

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

то есть 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), мы застряли.

Answer 3

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

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

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

Answer 4

Найдите приведенный ниже код C #, чтобы найти 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);
        }
    }

Answer 5

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

Answer 6

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

Answer 7

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

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