Поиск мажорирующего элемента в одномерном массиве

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

Северо-Казахстанский  государственный университет им. М. Козыбаева

 

 

 

 

 

 

Творческий  экзамен по дисциплине

 Высокоуровневые  методы программирования

 

на тему

«Поиск  мажорирующего элемента  в одномерном массиве»

 

 

 

 

 

 

 

 

 

 

 

ПЕТРОПАВЛОВСК, 2011

Мажорирующим элементом  в массиве A[1..N] будем называть элемент, встречающийся в массиве более N/2 раз. Легко заметить, что в массиве  может быть не более одного мажорирующего  элемента. Например, массив

3, 3, 4, 2, 4, 4, 2, 4, 4

имеет мажорирующий элемент 4, тогда как в массиве

3, 3, 4, 2, 4, 4, 2, 4

мажорирующего элемента нет.

Необходимо определить, есть ли в массиве мажорирующий элемент, и если есть, то какой.

 

Метод 1. Первый взгляд.

Поиск мажорирующего  элемента в неупорядоченном массиве.

Найдем какое-нибудь число D, которого нет в массиве (например, пусть D есть увеличенный на 1 максимальный элемент массива).

Алгоритм состоит  в следующем: на i-ом шаге подсчитывается

сколько среди  элементов A[i+1], A[i+2], ..., A[N] таких, значение которых равно значению элемента A[i]. Таким элементам присваивается значение D и в дальнейшем они рассматриваться не будут. Очевидно, что достаточно проверить только элементы A[1], ..., A[(N+1) div 2], так как оставшиеся элементы не могут быть мажорирующими.

Max:=A[1];

for i:=2 to n do { Поиск  максимального элемента массива  }

 if A[i] > Max

then Max:=A[i];

 D:=Max+1; { Находим число D, которого в массиве нет }

for i:=1 to (N+1) div 2 do { Берем в качестве возможного  решения }

begin { элементы из первой половины массива }

Count:=1;

if A[i]<>D { Подсчитываем, сколько раз элемент }

then { встречается  среди оставшихся }

for j:=i+1 to N do

 if A[i]=A[j]

then

begin

Count:=Count+1; { Увеличение  счетчика встретившихся } { элементов  }

A[j]:=D; { Заполнение элемента значением D }

 end;

if Count*2>N { Мажорирующий? }

then

begin

writeln('Мажорирующий элемент',A[i]) { Печать }

Halt; { Стоп }

end

end;

writeln('Мажорирующего элемента нет');

Этот алгоритм в худшем случае (когда все элементы масссива различны), выполняет (N-1) + (N-2) + ... + [(N+1)/2] операций сравнения. Если подсчитать сумму этой арифметической прогрессии, то мы получим величину порядка N*N. Обычно в этом случае говорится, что предложенный алгоритм имеет сложность О(N*N).

В программистском фольклоре можно найти упоминание об "американской методике решения задачи", состоящей в следующем:

"Если у  Вас есть задача, и Вы не  знаете, как ее решать, то от  сортируйте входные данные - может  быть это Вас натолкнет на  дельную мысль".

Может быть и нам стоит последовать этому мудрому совету и переупорядочить элементы так, чтобы все одинаковые шли друг за другом, после чего посмотреть, уменьшится ли число сравнений и, со ответственно, сложность алгоритма?

Метод 2. Сортировка.

Поиск мажорирующего элемента в упорядоченном массиве.

Отсортируем исходный массив по неубыванию, а затем просмотрим его, подсчитывая число идущих подряд одинаковых элементов.

Сортировка по неубыванию методом пузырька

for i:=1 to N-1 do

for j:=2 to N do

if A[i]>A[j]

then

begin

tmp:=A[i];

A[i]:=A[j];

A[j]:=tmp

end;

Count:=1; { Количество  одинаковых элементов }

for i:=2 to N do

 if A[i]<>A[i-1]

then if Count > N div 2

then

begin

writeln('Mажорирующий элемент ',A[i-1]); { Распечатать } Halt { Стоп }

 end;

else Count:=0 { Начать подсчет для следующего элемента}

else Count:=Count+1; { Увеличить счетчик  для текущего элемента }

Поиск мажорирующего  элемента можно организовать и по-другому:

если в отсортированном  массиве a[i]=a[i + N div 2], то элемент a[i] - мажорирующий. С учетом этого цикл просмотра массива запишется так:

for i:=1 to (N+1) div 2 do 
if A[i]<>A[i + N div 2] 
then begin 
writeln('Mажорирующий элемент ',A[i]); {Распечатать} 
Halt {Стоп} 
end; 
writeln('Мажорирующего элемента нет');

Сортировка методом пузырька требует выполнения порядка N*N операций сравнения и не дает никакого выигрыша относительно предыдущего алгоритма. При использовании более эффективной сортировки (например, "быстрой", см., например, книгу Н. Вирта "Алгоритмы + структуры данных = программы") потребуется порядка N*log_n операций сравнения. Но, наверное, тут мы делаем больше, чем требует постановка задачи - а именно получаем упорядоченную последовательность, тогда как нас интересуют только повторяющиеся элементы. Поэтому, вероятно, данный алгоритм не является наилучшим. По пытаемся найти лучшее решение.

Метод 3. Два массива.

Заведем массив-стек B. Первоначально он пуст.

В случае, если N - нечетное, N>1, то для элемента, не имеющего пары, проверяем  простым проходом по массиву и  подсчетом, не является ли он мажорирующим. Если нет, то уменьшаем N на 1 и сводим задачу к случаю четного N.

Предположим, что N - четное. Сравним A[1] и A[2]. Если они равны, то один из элементов заносим в массив-стек B на первое свободное место, иначе  ничего не делаем. Затем сравниваем A[3] и A[4]. Опять же, если они равны, то один из элементов добавляем к B, в противном случае ничего не делаем. Повторяем процесс до тех пор, пока не просмотрим все пары из массива A.

Утверждение: Если в массиве A есть мажорирующий элемент, то он будет являться мажорирующим и в массиве B.

Докажем это. Пусть N=2*k и в A есть m пар, составленных из совпадающих немажорирующих элементов. Мажорирующих элементов в A по крайней мере k+1. Следовательно, немажорирующих элементов, не вошедших в пары совпадающих элементов N-2*m-(k+1)=k-2*m-1. Итак, среди k пар есть:

m пар из немажорирущих  совпадающих элементов, не более k-2*m-1 пар из мажорирующего и немажорирующего элементов и

k-m-(k-2*m-1)=m+1 пара  из мажорирующих элементов.

То есть, при  приведенном выше преобразовании, элемент  мажорирующий в A является таковым и  в B.

Далее, перед  следующим шагом алгоритма, пересылаем содержимое массива B в массив A, массив B считаем пустым.

Для нового массива A повторяем описанные выше действия. В конце концов после очередного шага либо массив B пуст - и, следовательно, в исходном массиве не было мажорирующего  элемента, либо в B находится один единственный элемент, который, возможно, и является мажорирующим. С целью проверки пройдем еще раз по исходному массиву и подсчитаем, сколько раз интересующий нас элемент там встретится - больше N/2 раз или нет. Необходимость добавочного прохода по массиву можно показать на примере следующего массива: 2 2 3 4 3 4.

Оценим число  обращений к элементам исходного  массива: на каждом шаге алгоритма мы совершаем просмотр всех элементов  текущего массива. Если размерность  массива нечетная, то она уменьшается на 1, если же четная - то вдвое. Таким образом, при выполнении каждых двух шагов алгоритма размерность массива уменьшается по край ней мере вдвое, и общее число обращений к элементам массива не будет превышать величины 2*(N + N/2 + N/4 + ...) = 4N (сумма, стоящая в скобках, есть сумма геометрической прогрессии со знаменателем 1/2). Для определения того, на самом ли деле полученный элемент является мажорирующим, требуется еще один проход по исходному массиву. Итого, число операций не превышает 5*N.

 

Метод 4. Стек.

Мы заведем  стек и будем добавлять и извлекать из стека элементы по следующему правилу:

1) На первом  шаге помещаем в стек A[1] . 
2) На i-ом шаге, i=2, ..., N повторяем следующие действия: 
Если стек пуст, 
то помещаем в него A[i] 
иначе 
если элемент A[i] совпадает с элементом на верхушке стека 
то добавляем A[i] в стек 
иначе удаляем элемент с верхушки стека.

Если стек не пуст, то в нем находятся лишь совпадающие элементы. Если у нас  в последовательности есть мажорирующий элемент, то он и останется в стеке после N-го шага (мажорирующие элементы встречаются в последовательности более N/2 раз, и не могут при выполнении N шагов алгоритма "сократиться" со всеми остальными немажорирующими элементами).

Для проверки (в  случае непустого стека после  выполнения N-го шага) является ли элемент в стеке мажорирующим (если в стеке более одного элемента, то они все совпадают), мы просматриваем массив еще один раз и подсчитываем, сколько раз встречается в массиве элемент из стека. Если это число больше N/2, то этот элемент мажорирующий, иначе - мажорирующего элемента в последовательности нет.

Замечание. В  данном случае нет никакой необходимости  использовать такую структуру данных как стек, т.к. в нем, по алгоритму, могут храниться лишь совпадающие  элементы. Вместо стека можно (и лучше) завести две переменные - в одной хранить элемент (который ранее хранился в стеке), в другой переменной подсчитывать количество повторений этого элемента. Именно так мы и поступим.

Алгоритм можно  записать так:

begin

element:=A[1]; { Присвоение начальных значений }

Count:=1;

for i:=2 to N do

if Count=0 { Счетчик нулевой? }

then

begin { Да }

element:=A[i]; { Начать  подсчет для нового }

Count:=1; { элемента }

end

else { Если счетчик  ненулевой }

 if element=A[i] { Элементы совпадают? }

 then Count:=Count+1 { Да. Увеличить счетчик }

 else Count:=Count-1; { Нет. Уменьшить счетчик }

if Count=0

then writeln(' Мажорирующего элемента нет')

else

begin

Count:=0;

for i:=1 to n do { Добавочный проход }

if A[i]=element

then Count:=Count+1;

if Count*2>N

then writeln('Мажорирующий элемент',element)

else writeln('Мажорирующего  элемента нет');

end;

end.

 

Указанным выше способом можно искать в массиве A и элемент, удовлетворяющий такому условию:

Элемент встречается  в A не менее N/2 раз (в предыдущей формулировке задачи он должен был встречаться более N/2 раз). При четном N таких элементов, очевидно, может быть два.

В случае вышеприведенной  формулировки задачи мы проделываем  ту же самую последовательность действий, что и ранее: в случае, если после N-го шага стек не пуст, то оставшийся в нем элемент является претендентом на искомый, и мы просматриваем массив еще раз, подсчитывая, сколько раз он там встречается.

В случае, если стек пуст, то вполне возможно, что требуемому свойству удовлетворяет два элемента, и именно они то и принимали участие в сравнении на N-ом, последнем шаге. Мы совершаем еще один проход по массиву, подсчитывая, сколько раз встречаются в нем элементы element и A[n]. Затем делаем две проверки:

Если количество для element не меньше N/2, то element - искомый элемент. Если количество для A[n] не меньше N/2, то A[n] искомый элемент.

 

Заключение.

Составим таблицу  сложностей алгоритмов, предложенных для решения сформулированной задачи:

Алгоритм	Сложность
Без упорядочения	O(N*N)
С упорядочением в зависимости от способа сортировки	от O(N*log N) до O(N*N)
С использованием двух	<=O(5*N)
С использованием стека	O(2*N)