У нас есть две базы данных размера n, содержащие числа без повторов. Итак, всего у нас 2n элементов. Доступ к ним можно получить через запрос к одной базе данных за раз. Запрос таков, что вы даете ему k, и он возвращает k-ю наименьшую запись в этой базе данных. Нам нужно найти n-ю наименьшую запись среди всех 2n элементов в запросах O (log n).
Идея состоит в том, чтобы использовать разделяй и властвуй, но мне нужна помощь, чтобы обдумать это. Спасибо!
Вот как я это обдумал. Поскольку это образовательная проблема, я предлагаю вам прекратить чтение, если какой-либо из пунктов заставит вас подумать: «ага, я не подумал об этом, я могу думать дальше в этом направлении сам».
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)-й наименьший элемент результирующей пары массивов, и это будет k-й наименьший из исходных массивов.
4) Наконец, прорывное наблюдение заключается в том, что если m-й наименьший элемент массива A меньше, чем m-й наименьший элемент массива B, то этот m-й элемент A не может быть (2m)-м наименьшим элементом двух массивов вместе взятых. Это меньше (или равнозначно: я не уверен, означает ли «без повторов» «без повторов в каждой базе данных» или «без повторов между объединенными базами данных»), поскольку существует не более 2*(m- 1) элементы строго меньше его в обоих массивах вместе взятых.
Если я не ошибся, остальное кодирование. С небольшим дополнительным аргументом для учета смещения на 1, когда k нечетно, это решение фактически равно O(log k), что равно O(log n), поскольку k ‹= 2*n.
Я видел эту задачу на квалификационном экзамене не так давно, и она пахнет домашней задачей. Поэтому я сделаю только два предложения:
Изучите бинарный поиск, обращая особое внимание на точную природу инвариантов цикла. В книге Джона Бентли Programming Pearls есть хорошее объяснение
Попробуйте обобщить инварианты для бинарного поиска.
Нарисуйте картинку с различными частными случаями:
Это довольно сложная проблема; вам будет легче, если вы пойдете прямо за доказательством правильности.
Советы:
