nth наименьшее число среди двух баз данных размером n каждый с использованием divide и conquer

Question

У нас есть две базы данных размером n, содержащие числа без повторений. Итак, в целом мы имеем 2n элементов. К ним можно получить доступ через запрос к одной базе данных за раз. Запрос таков, что вы даете ему k, и он возвращает k-ю наименьшую запись в этой базе данных. нам нужно найти n-ю наименьшую запись среди всех 2n-элементов в O (logn) запросах. идея состоит в том, чтобы использовать разделение и побеждать, но мне нужна помощь в этом. благодаря!

Answer 1

Вот как я это продумал. Поскольку это образовательная проблема, я предлагаю вам прекратить читать, если какой-либо из соображений заставит вас думать: «Ага, я не думал об этом, я могу думать дальше по этим строкам».

1) Такое же наблюдение, как и sdcwc: с возможным небольшим колебанием в отношении того, начинается ли оно с 0 или 1, базу данных можно рассматривать как отсортированный массив. Я прошу элемент 0, я получаю наименьшее количество. Я прошу 12, я получаю 13-е место. И так далее. Мне это легче понять.

2) Мы знаем, что мы ищем алгоритм O (log n). Это означает, что, грубо говоря, мы ищем одну из двух вещей:

• Либо мы начинаем путем вычисления наименьшего элемента, а затем вычислить 2-ой маленький, 4-ый наименьший, 8, и т.д., пока мы до к размеру, который мы хотим, каждый шаг в постоянное время. Мне это не кажется многообещающим.

• Или мы начинаем с проблемы размера n, тогда мы выполняем некоторую операцию с постоянным временем, которая позволяет нам решить исходную задачу, решая проблему размера n/2.Очевидно, что мы можем решить задачу для n = 1 в постоянное время, чтобы завершить алгоритм. Это звучит немного правдоподобно.

На самом деле это не обязательно должно быть n/2 каждый раз. Это может быть n/3, или 999 * n/1000, и результат будет по-прежнему равен O (log n). Но нет никакого вреда в поиске n/2 в первую очередь.

3) Как мы собираемся уменьшить проблему? Ну, если мы можем убрать/удалить m элементов с самого начала одного массива или меньше, чем на k-м наименьшем, тогда мы найдем (km) -ый наименьший элемент результирующей пары массивов, и это будет kth самый маленький из исходных массивов.

4) Наконец, прорывное наблюдение состоит в том, что если m-й наименьший элемент массива A меньше, чем m-й наименьший элемент массива B, то этот m-й элемент из A не может быть (2m) -м наименьшим элементом два массива вместе взятые. Он меньше этого (или равного значения: я не уверен, означает ли «нет повторов» означает «нет повторений в каждой базе данных» или «нет повторений между объединенными базами данных»), так как не более 2 * (м- 1) элементы строго меньше, чем в обеих массивах.

Если я не сделал ошибку, остальное кодирование. С небольшим дополнительным аргументом для учета off-by-1, когда k нечетно, это решение на самом деле O (log k), которое равно O (log n), так как k < = 2 * n.

Answer 2

Недавно я увидел эту проблему на квалификационном экзамене, и это пахнет проблемой домашних заданий. Поэтому я сделаю только два предложения:

• Изучите бинарный поиск с уделением особого внимания точной природе инвариантов цикла. Книга Джона Бентли Программирование Pearls имеет хорошее объяснение

• Попробуйте обобщить инварианты для бинарного поиска.

• Нарисуйте картину с различными частными случаями:

  • Каждого число в DB1 меньше, чем каждый номере в DB2
  • наоборот
  • DB1 равна DB2
  • Каждый номер в DB2 в два раза соответствующее число в DB1

Это довольно сложная проблема; вам будет легче, если вы пойдете прямо для доказательства правильности.

Answer 3

Советы:

• Наблюдайте свои "базы данных" действительно два отсортированных массива.
• Возьмите элементы из «среднего» массива и сравните их. Результат сравнения может позволить вам «исключить» часть.