Изменения

Перейти к: навигация, поиск

Мажорирующий элемент

505 байт добавлено, 15:15, 22 марта 2015
Нет описания правки
'''for''' i = 0 '''to''' N - 1
'''if''' count == 0 ''<font color="green">// никто не стоит'' candidate = a[i] ''<font color="green">// встанет текущий элемент'' count++ ''<font color="green">// увеличим количество стоящих'' '''else''' ''<font color="green">// кто-то стоит'' '''if''' a[i] == candidate ''<font color="green">// стоит такой же элемент'' count++ ''<font color="green">// увеличим количество стоящих'' '''else''' ''<font color="green"> // стоит другой элемент => подобрали пару'' count-- ''<font color="green">// уменьшим количество стоящих''
'''return''' candidate
findMajorityElement(a, N, K)
''<font color="green"> // candidates - словарь, где ключ - стоящий элемент,'' ''<font color="green"> // значение - количество таких стоящих элементов''
'''for''' i = 0 '''to''' N - 1
'''if''' candidates.containsKey(a[i]) ''<font color="green">// нашли стоящий элемент'' candidates[a[i]]++ ''<font color="green">// увеличим счетчик''
'''else'''
'''if''' candidates.size() < K - 1 ''<font color="green">// полная группа не образована'' candidates[a[i]] = 1 ''<font color="green">// добавим элемент в группу'' '''else''' ''<font color="green">// образовалась полная группа'' '''for''' element '''in''' candidates ''<font color="green">// посадим группу''
candidates[element]--
'''if''' candidates[element] == 0 ''<font color="green">// если никто с таким элементом не стоит'' candidates.remove(element) ''<font color="green">// удалим этот элемент''
'''for''' candidate '''in''' candidates ''<font color="green">// обнулим счетчик''
candidates[candidate] = 0
'''for''' i = 0 '''to''' N - 1 ''<font color="green">// посчитаем, сколько раз встречаются элементы''
'''if''' candidates.containsKey(a[i])
candidates[a[i]]++
'''for''' candidate '''in''' candidates ''<font color="green">// проверим, встречается ли элемент N / K раз''
'''if''' candidates[candidate] > N / K
elements.add(candidate)
13
правок

Навигация