174
правки
Изменения
→Доказательство
=== Доказательство ===
На <tex>i</tex>''-ом'' шаге поддерживается следующий инвариант: если на подмассиве <tex>a[0..i]</tex> существуют элементы, которые встречаются больше, чем <tex>N / 2</tex> раз, то все они содержатся в <tex>candidates</tex> и размер <tex>candidates</tex> не превышает <tex>K</tex>. Тогда на <tex>N</tex>''-ом'' шаге шаге <tex>candidates</tex> будет содержать все возможные элементы, встречающиеся более, чем <tex>N / K</tex> раз, остается только выполнить проверку. Покажем, что данный инвариант всегда выполняется:
Пусть данный инвариант выполняется на <tex>k</tex>''-ом'' шаге. Тогда на <tex>(k+1)</tex>''-ом'' шаге возможны <tex>3</tex> варианта:
#<tex>a[i] \in candidates</tex><p>бла-бла-бла</p>
#<tex>a[i] \notin candidates</tex> и <tex>candidates.size() < K - 1</tex><p>бла-бла-бла</p>
#<tex>a[i] \notin candidates</tex> и <tex>candidates.size() = K - 1</tex><p>бла-бла-бла</p>
Каждая итерация в среднем выполняется за O(1) при реализации словаря на основе хэш-таблиц. Итоговая сложность O(N) с дополнительной памятью O(K).
== Альтернативное решение ==
