174
правки
Изменения
→Псевдокод
=== Псевдокод ===
findMajorityElement(a, N, K)
// candidates - словарь, где ключ - стоящий элемент,
// значение - количество таких стоящих элементов
for i = 0 to N - 1
if candidates.containsKey(a[i]) // нашли стоящий элемент
candidates[a[i]]++ // увеличим счетчик
else
if candidates.size() < K - 1 // полная группа не образована
candidates[a[i]] = 1 // добавим элемент в группу
else // образовалась полная группа
for element in candidates // посадим группу
candidates[element]--
if candidates[element] == 0 // если никто с таким элементом не стоит
candidates.remove(element) // удалим этот элемент
return candidates
=== Доказательство ===
