Majority Element

Majority element: the element that appears strictly more than n/2 times in the array.

An Θ(n)-time algorithm to find the majority element or reports that no such element exists:

Hint: Find a candidate solution, then determine whether this candidate is indeed the majority element.

FIND-MAJORITY-ELEMENT(A)

1 for i ← 1 to length[A]

2 if stack is empty

3    then push A[i] on the stack

4 else if A[i] equals top element on the stack

5    then push A[i] on the stack

6 else pop the stack

7 if stack is empty

8    then return NoMajority

9 candidate ← top element on the stack

10 counter ← 0

11 for i ← 1 to length[A]

12   if A[i] equals candidate

13        then counter ← counter + 1

14 if counter > length[A]/2

15   then return candidate

16 return NoMajority

Claim: If a majority element exists, it will be on the stack at the end of this part of the procedure.

Call the majority element x,  appears i > n/2 times.

Each time x is encountered, it is either pushed on the stack or an element (different from x) is popped off the stack.

There are n − i < i elements different from x.

Assume x is not on the stack at the end of the procedure.

Then, each of the i elements of x must have either popped another element off the stack, or been popped off by another element. However, there are only n − i < i other elements, so this is a contradiction.

Therefore, x must be on the stack at the end of the procedure.

Running time: Θ(n).

Problem 1510 – Timus – Order:

program _1510;

const nmax=500000;

var s: array[0..nmax] of longint;

i, a, n: longint;

begin

s[0]:=0;

for i:=1 to n do

begin

if s[0]=0 then begin s[0]:=1; s[1]:=a; end

else if a=s[s[0]] then begin inc(s[0]); s[s[0]]:=a; end

else if i<>n then dec(s[0]); {when x appears exactly n/2 times}

end;

writeln(s[s[0]]);

end.