Изменения

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

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

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

Навигация