режим мультимножестве в данный момент времени, связанного (большинство кратности)

Question

Найти Данная проблема:

Мультимножество представляет собой набор, в котором некоторые из элементов происходит более чем один раз (например, {A, F, B, B, e, c, b, g, a, i, b} - мультимножество). Элементы взяты из полностью упорядоченного множества. Представить алгоритм, когда он представлен мультимножеством как вход, находит элемент, который имеет наибольшее количество вхождений в мультимножестве (например, в {a, f, b, b, e, c, b, g, a, c, b} b имеет наибольшее количество вхождений). Алгоритм должен выполняться в O (n lg n/M + n) времени, где n - количество элементов в мультимножестве, а M - наибольшее количество вхождений элемента в мультимножество. Обратите внимание, что вы не знаете значение M.

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

Наше первоначальное решение:.

Наша идея состояла в том, чтобы использовать большинство Мура алгоритм для определения того, имеет ли мультимножество мажоритарный кандидат (например, {a, b, b} имеет большинство, b). После определения, было ли это истинно или ложно, мы либо выводим результат, либо находим медиану списка, используя данный алгоритм (известный как «Выбрать»), и разбиваем список на три подсписка (элементы меньше и равны медианной, а элементы, медиана). Опять же, мы проверили бы каждый из списков, чтобы определить, присутствует ли элемент большинства, если это так, то есть ваш результат.

Например, учитывая мультимножество {а, б, в, г, д, е, е}

Шаг 1: проверьте большинство. Ничего не найдено, разделите список на основе медианы.

Шаг 2: L1 = {a, b, c, d, d}, L2 = {e, f} Найдите большинство из них. Ничего не найдено, снова разделите списки.

Шаг 3: L11 = {a, b, c} L12 = {d, d} L21 = {e} L22 = {f} Проверьте каждый элемент большинства. L12 возвращает d. В этом случае d является наиболее встречающимся элементом в исходном мультимножестве, таким образом, является ответом.

Проблемы, с которыми мы сталкиваемся, - это достаточно быстрый алгоритм этого типа, а также то, можно ли это сделать рекурсивно или если требуется завершение цикла. Как говорится в подсказке, суб-проблемы не могут быть меньше «определенного» размера, который мы считаем M (большинство случаев).

Answer 1

Если вы используете рекурсию в наиболее прямой способ, как описано в вашем посте, он не будет иметь желаемую временную сложность. Зачем? Предположим, что элемент ответа является самым большим. Затем он всегда находится в правой ветви рекурсии. Но сначала мы называем левую ветвь, которая может идти гораздо глубже, если все элементы там различны (получая куски размером 1, в то время как мы не хотим, чтобы они были меньше M).

Вот правильное решение:

Давайте всегда разделить массив на три части на каждом шаге, как описано в вашем вопросе. Теперь давайте отступим и посмотрим, что у нас есть: рекурсивные вызовы образуют дерево. Чтобы получить желаемую временную сложность, мы никогда не должны углубляться, чем уровень, на котором находится ответ.Чтобы достичь этого, мы можем пересечь дерево, используя поиск по ширине с очередью вместо поиска глубины. Вот и все.

Answer 2

Если вы хотите сделать это в реальной жизни, стоит рассмотреть хэш-таблицу, чтобы отслеживать подсчеты. Это может привести к амортизации O (1) сложности для доступа к хэш-таблице, поэтому общая сложность следующего кода Python равна O (n).

import collections 
C = collections.Counter(['a','f','b','b','e','c','b','g','a','i','b']) 
most_common_element, highest_count = C.most_common(1)[0]