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.

Proof: (by contradiction)

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).

 

(from carlstrom.com/stanford/cs161/ps1sol.pdf)

 

Problem 1510 Timus Order:

http://acm.timus.ru/problem.aspx?space=1&num=1510

 

program _1510;

const nmax=500000;

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

i, a, n: longint;

begin

readln(n);

s[0]:=0;

for i:=1 to n do

begin

readln(a);

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.