энное самое маленькое количество среди двух баз данных размера n каждое использование делит и завоевывает [закрытый]
3 ответа
Вот как я это продумал.Поскольку это образовательная проблема, я предлагаю вам прекратить читать, если какой-либо из пунктов заставляет вас думать: «Ага, я не думал об этом, я могу подумать дальше в том же духе сам».
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 имеет хорошее объяснение
Попробуйте обобщить инварианты для двоичного поиска.
Нарисуйте картину с различными частными случаями:
- Каждое число в DB1 меньше, чем каждое число в DB2
- Наоборот
- DB1 равно DB2
- Каждое число в DB2 в два раза больше соответствующего числа в DB1
Это довольно сложная проблема; вам будет легче, если вы сразу обратитесь за доказательством правильности.