Поиск k-го наименьшего элемента в объединении отсортированных массивов

Я изучал статью о нахождении k-го наименьшего элемента в объединении двух отсортированных массивов в leetcode . Я не думаю, что алгоритм правильный. Существует такая линия: мы замечаем, что при Ai <Bj, то должно быть верно, что Ai <Bj-1. С другой стороны, если Bj <Ai, то Bj <Ai-1. , Как это может быть справедливо для любых i и j ?

Во-вторых, эта линия также меня озадачивает: мы пытаемся подойти к этой сложной проблеме, сравнив средние элементы A и B, которые мы идентифицируем как Ai и Bj. Если Ai находится между Bj и Bj-1, мы только что нашли i + j + 1 наименьший элемент , хотя это и правда. Может ли кто-нибудь объяснить причину? Я действительно хочу понять algo, я сделал это, объединив массивы, но это занимает время O(N) по сравнению с O(log N) .

2 Solutions collect form web for “Поиск k-го наименьшего элемента в объединении отсортированных массивов”

Заметим, что при Ai < Bj , то должно быть верно, что Ai < Bj-1 . С другой стороны, если Bj < Ai , то Bj < Ai-1 . Как это может быть справедливо для любых i и j ?

Это неверно для всех пар i и j . В статье рассматривается особая ситуация.

Во-первых, предполагается, что дубликатов нет, даже в виде общих элементов A и B Во-вторых, вывод о том, что

 Ai < Bj ==> Ai < Bj-1, resp. Bj < Ai ==> Bj < Ai-1 

производится при условии, что ни один из

 Bj-1 < Ai < Bj resp. Ai-1 < Bj < Ai 

держит. Итак, исключив эти конфигурации, Ai < Bj ==> Ai <= Bj-1 и Bj < Ai ==> Bj <= Ai-1 немедленно следуют, а последующие строгие неравенства следуют предположением, что не существует дубликатов.

Мы пытаемся подойти к этой сложной проблеме, сравнивая средние элементы A и B, которые мы идентифицируем как Ai и Bj. Если Ai находится между Bj и Bj-1, мы только что нашли i + j + 1 наименьший элемент

В массиве B есть j элементов, меньших Bj , и в массиве A есть i элементов, меньших Ai (индексы начинаются с 0). Итак, если Bj-1 < Ai < Bj , то вместе оба массива содержат ровно j + i элементов, меньших Ai .

Что изменится, если есть дубликаты?

Немного.

Мы по-прежнему рассматриваем ситуацию, когда i + j = k-1 . Предположим, что Ai <= Bj .

  1. Что, если Ai = Bj ?
  2. Что, если Ai < Bj ?

В случае 1 пусть m – наименьший индекс, такой, что Am = Ai и n наименьший индекс такой, что Bn = Bj . Тогда в обоих массивах вместе есть ровно m + n <= i + j = k-1 элементы, строго меньшие Ai , и по крайней мере (i+1) + (j+1) = (k+1) элементы не больше чем Ai . Следовательно, k-й наименьший элемент равен Ai .

Для 2. рассмотрим три случая: a) Bj-1 < Ai , b) Bj-1 = Ai , c) Bj-1 > Ai .

В случае а) мы имеем j элементов из B , которые не больше Ai , и они все строго меньше, и мы имеем m <= i элементов в A , которые строго меньше Ai ( m как указано выше), и нечетное число , но не менее i-m+1 элементов, равных Ai . Таким образом, в обоих массивах одновременно есть ровно j + m <= j + i = k-1 элементов, которые строго меньше Ai и по крайней мере j + m + (i-m+1) = j+i+1 = k элементы не больше Ai , поэтому k-й наименьший элемент обоих массивов вместе равен Ai .

В случае б) то же рассуждение показывает, что k-й наименьший элемент обоих массивов вместе равен Ai .

В остальном случае Ai < Bj-1 вещи становятся чуть сложнее. Массив B содержит не менее j элементов, не больших Bj-1 , а массив A содержит по крайней мере i+1 элементов, строго меньших Bj-1 , поэтому k-й наименьший элемент обоих массивов вместе не Bj-1 . Но он не может быть меньше Ai ( B содержит не более j-1 элементов, меньших Ai , поэтому вместе оба массива содержат не более i + (j-1) = k-2 элементов, меньших Ai ).

Поэтому мы можем отбросить часть ниже Ai из массива A и части выше Bj-1 из массива B и действовать так же, как без дубликатов.

Все, что изменилось, состояло в том, что несколько строгих неравенств пришлось заменить слабыми неравенствами.

Код (был бы более эффективным, если бы начальные индексы и длины были переданы вместо нарезки, но нарезка дает более короткий код):

 def kthsmallest(A, B, k): if k < 1: return None a_len, b_len = len(A), len(B) if a_len == 0: return B[k-1] # let it die if B is too short, I don't care if b_len == 0: return A[k-1] # see above # Handle edge case: if k == a_len + b_len, we would # get an out-of-bounds index, since i + j <= a_len+b_len - 2 # for valid indices i and j if a_len + b_len == k: if A[-1] < B[-1]: return B[-1] else: return A[-1] # Find indices i and j approximately proportional to len(A)/len(B) i = (a_len*(k-1)) // (a_len+b_len) j = k-1-i # Make sure the indices are valid, in unfortunate cases, # j could be set to b_len by the above if j >= b_len: j = b_len-1 i = k-1-j if A[i] <= B[j]: if j == 0 or B[j-1] <= A[i]: return A[i] # A[i] < B[j-1] <= B[j] return kthsmallest(A[i:], B[:j], ki) # B[j] < A[i], symmetrical to A[i] < B[j] if i == 0 or A[i-1] <= B[j]: return B[j] # B[j] < A[i-1] return kthsmallest(A[:i], B[j:], kj) 

Вы интерпретируете эти утверждения изолированно, но они строятся друг на друге. Вот текст, который (я думаю) вы имеете в виду:

Поддержание инварианта i + j = k – 1, если Bj-1 <Ai <Bj, то Ai должно быть k-м самым маленьким, или если Ai-1 <Bj <Ai, то Bj должно быть k-м наименьшим , Если выполнено одно из вышеуказанных условий, мы закончили. Если нет, мы будем использовать i и j в качестве сводного индекса для разделения массивов. Но как? Какую часть мы должны отбросить? Как насчет самих Ай и Бь?

Заметим, что при Ai <Bj, то должно быть верно, что Ai <Bj-1. С другой стороны, если Bj <Ai, то Bj <Ai-1. Зачем?

Прерывание этого в подпозициях дает следующую интерпретацию (имея в виду, что индексирование начинается с 0 , но что A0 является первым наименьшим элементом, а A1 является вторым наименьшим элементом и т. Д.):

  1. i + j = k - 1 (инвариантно, по определению)
  2. Положим, что Bj-1 < Ai < Bj . Тогда Ai должно быть k м наименьшим. Это связано с тем, что Ai больше i элементов в A и больше, чем j элементов в B Таким образом, это больше, чем всего i + j = k - 1 единиц. Это означает, что его индекс в объединенном списке A|B будет k - 1 , и поэтому это будет k й элемент в этом списке.
  3. Положим, что Ai-1 < Bj < Ai . Тогда Bj должно быть k м наименьшим, по той же линии рассуждений в 2.
  4. Предположим теперь, что оба (a) Bj-1 < Ai < Bj и (b) Ai-1 < Bj < Ai ложны . Тогда совершенно очевидно, что если Ai < Bj то A1 < Bj-1 , поскольку в противном случае (a) было бы истинным. Аналогично, если Bj < Ai то Bj < Ai-1 , так как в противном случае (b) было бы истинным.

Я беру вас за ваше слово, что вы хотите объяснить эти утверждения, а не алгоритм в целом. (Но я скажу больше, если хотите.)

Обратите также внимание на то, что, как напоминает мне ответ Даниэля Фишера , приведенные рассуждения справедливы только в том случае, если нет дубликатов; назовите это предложение 0.

  • Найти первый не повторяющийся символ в строке
  • Выбирайте N элементов в случайном порядке из последовательности неизвестной длины
  • Эффективный групповой перекрывающий прямоугольник
  • Разница между двумя ближайшими к нулю продуктами: решение без грубой силы?
  • Простой способ сплавления нескольких близких точек?
  • Алгоритм. Как эффективно удалять повторяющиеся элементы в списке?
  • Моя реализация слияния двух отсортированных списков в линейном времени - что можно улучшить?
  • Как создать предсказуемую перетасовку последовательности без предварительного создания всей последовательности?
  •  
    Interesting Posts for Van-Lav

    heapq с обычным предикатом сравнения

    Передача аргументов при вызове функции через dict

    точки соединения питонов питона

    Совокупные наборы в соответствии с ключами с python defaultdict

    tweepy stream to sqlite database – синтаксическая ошибка

    Как я могу прочитать файл в строке, начинающейся с данного слова, не зная номера строки?

    получение данных из .txt-файла с помощью python?

    Как добавить данные пакета рекурсивно в Python setup.py?

    python rtype docstring / реструктурированный текст для фабрик классов / селекторов

    Каковы параметры URL? (элемент в позиции № 3 по результату urlparse)

    Параллельность. Расширяются ли расширения Python на C / C ++, связанные с блокировкой Global Interpreter?

    Подсчитайте заглавные буквы в строке

    Импорт модулей сопоставления в Python для простого рефакторинга

    Как изменить температуру выхода softmax в Keras

    Как заставить Fabric автоматически (вместо интерактивного взаимодействия) взаимодействовать с командами оболочки? Объединить с pexpect?

    Python - лучший язык программирования в мире.