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