Изменения
Орфография
== Обобщение на случай поиска элемента, встречающегося N/K раз ==
Будем пользоваться той же идеей, что и в предыдущем пункте. До этого мы садили сажали людей парами, а теперь будем садить сажать группами из <tex>K</tex> человек. В итоге, если искомые нами элементы есть, то они останутся стоять.
Будем идти по массиву и хранить элементы, которые еще не сели. При встрече элемента, который уже есть среди стоящих, увеличиваем счетчик данного элемента на <tex>1</tex>. В противном случае смотрим, можем ли мы посадить группу и, либо ее садимсажаем, либо добавляем текущий элемент к стоящим. В конце требуется сделать проверку, что оставшиеся стоять элементы встречаются <tex>N/K</tex> раз.
=== Псевдокод ===
=== Доказательство ===
На <tex>i</tex>''-ом'' шаге поддерживается следующий инвариант: если на подмассиве <tex>a[0..i]</tex> существуют элементы, которые встречаются больше, чем <tex>i / K</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[k + 1] \in candidates</tex><p>Размер <tex>candidates</tex> не увеличен, текущий элемент останется стоять. Инвариант выполняется.</p>
#<tex>a[k + 1] \notin candidates</tex> и <tex>candidates.size() < K - 1</tex><p>Размер <tex>candidates</tex> останется меньше <tex>K</tex>, текущей элемент останется стоять. Инвариант выполняется.</p>
#<tex>a[k + 1] \notin candidates</tex> и <tex>candidates.size() = K - 1</tex><p>Размер <tex>candidates</tex> на данном шаге может только уменьшиться. Садим Сажаем группу. Если какой-то элемент был удален на текущем шаге, то, значит, он встречался не более, чем <tex>(k + 1) / K</tex> раз, т.к. мы могли успеть посадить максимум <tex>(k + 1) / K</tex> групп. Тогда удаление данного элемента из candidates ни к чему плохому не приведет. Инвариант выполняется.</p>
Рассмотрим среднее количество обращений к словарю за одну итерацию. На каждой итерации происходит не более <tex>1</tex> увеличения счетчика. Тогда, за все время, происходит не более <tex>N</tex> увеличений. Так как количество уменьшений счетчика не может превышать количество увеличений, то всего происходит не более <tex>2N</tex> обращений к словарю. Следовательно, сложность одной итерации составляет <tex>O(1)</tex>.
