Finding the count of required entries within a list?

Question

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algorithm?? The problem is self-blocking I feel??

Answer 1

Hint: Take a look at Boyer and Moore's Linear Time Vote Algorithm

Steps:

1. Find median of array using median of medians algorithm in 0(n) time
2. partition using median as pivot element
3. use moore's voting algo in each part between
   a) median and first element and
   b) median and last element
4. check if median is the required element.

For more detailed algorithms to solve this problem you can refer to this document. Really, this would be very helpful.

Refer to this similar post also for more answers.