Изменения

На <tex>i</tex>''-ом'' шаге поддерживается следующий инвариант: если на подмассиве <tex>a[0..i]</tex> существуют элементы, которые встречаются больше, чем <tex>N i / K</tex> раз, то все они содержатся в <tex>candidates</tex> и размер <tex>candidates</tex> не превышает <tex>K</tex>. Тогда на <tex>N</tex>''-ом'' шаге шаге <tex>candidates</tex> будет содержать все возможные элементы, встречающиеся более, чем <tex>N / K</tex> раз, остается только выполнить проверку. Покажем, что данный инвариант всегда выполняется:

Каждая итерация Пусть операции со словарем выполняются за <tex>O(X)</tex>. Тогда покажем, что в среднем итерация выполняется тоже за <tex>O(X)</tex>. Заметим, что увеличение счетчика эквивалентно добавлению элемента в <tex>candidates</tex>, а уменьшение счетчика - удалению элемента. Тогда на кажой итерации происходят добавления или удаления элементов. В рамках одной итерации мы добавляем не более <tex>1</tex> элемента. Тогда, количество элементов не превышает <tex>N</tex>. Максимум, что мы можем сделать - это добавить <tex>N</tex> элементов и их же удалить. Получается <tex>O(N) </tex> операций. Всего итераций <tex>N</tex> штук. Тогда на каждую итерацию в среднем приходится <tex>O(1)</tex> операций и итоговая сложность итерации <tex>O(X)</tex>. Получается, при реализации словаря на основе хэш-таблиц, каждая итерация в среднем выполняется за <tex>O(1)</tex>. Итоговая сложность <tex>O(N) </tex> с дополнительной памятью <tex>O(K)</tex>.