Special Algorithms

Boyer-Moore Majority Vote Algorithm

229. Majority Element II

Useful for Big Data streaming where memory space is concerned. 1st pass is to find the candidate.

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a) If a[maj_index] == a[i]
          count++
    (b) Else
        count--;
    (c) If count == 0
          maj_index = i;
          count = 1
3.  Return a[maj_index]

2nd pass to double check, if the series of nums is not guaranteed to have a majority element (freq>n/2)

printMajority (a[], size)
1.  Find the candidate for majority
2.  If candidate is majority. i.e., appears more than n/2 times.
       Print the candidate
3.  Else
       Print "NONE"