Разработайте алгоритм «разделяй и властвуй», чтобы найти настоящую карту

Я думаю о задаче D&S, чтобы найти настоящую карту в группе карт. Все настоящие карты имеют одинаковый код, а поддельные карты имеют много кодов (могут быть одинаковыми или разными). Количество реальных карт больше половины. Я могу только сравнить две карты, чтобы увидеть, имеют ли они одинаковый код, но не могу определить, что это за код.

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


algorithm divide-and-conquer
person RunningPig    schedule 23.10.2017    source источник
comment
Похоже на Большинство голосов Бойера-Мура. Я не вижу необходимости в D&C.   -  person user58697    schedule 23.10.2017
comment
@user58697 user58697, но требуется D&C   -  person RunningPig    schedule 24.10.2017
comment
Вот подсказка: если вы разделите ввод на две половины, по крайней мере одна половина все равно будет содержать мажоритарный элемент. Таким образом, если вы решите проблему большинства элементов на обеих половинах, у вас будет не более двух кандидатов.   -  person Rob Neuhaus    schedule 24.10.2017
comment
@RobNeuhaus Вот оптимизация. Сначала вы обрабатываете одну половину, а затем смотрите, работает ли ее ответ в целом. Если вы сообразительны и лишь умеренно удачливы, вы быстро определите основной элемент, а затем вам нужно будет выполнить достаточное количество сравнений, чтобы убедиться, что это большинство.   -  person btilly    schedule 25.10.2017
comment
Да, я думаю, что это превращает его из O (n log n) в O (n) в ожидании.   -  person Rob Neuhaus    schedule 25.10.2017

Ответы (1)


arrow_upward
0
arrow_downward

Просто измените quicksort для своих целей.

Выберите случайный элемент в качестве опорного, найдите 3 ведра меньше, равно или больше. Если больше половины равны, все готово. В противном случае выбросьте все, кроме самого большого ведра, и повторите.

Средний случай будет O(n). В худшем случае O(n^2). При необходимости вы можете улучшить наихудший случай с помощью обычного алгоритма медианы медиан, который существует для быстрой сортировки.

person btilly    schedule 23.10.2017
comment
Это предполагает, что набор хорошо упорядочен — что между любыми двумя элементами существует отношение «меньше». Ваше обоснование работает, но я думаю, что единственный раздел, который мы получаем, равен или не равен. - person Prune; 24.10.2017