Looking for the number of required entries in the list?

Question

Create an algorithm that, given a list of n elements in the array, will find all elements that appear more than 3 times in the list. The algorithm must be executed in linear time (n> = 0)

It is expected that you will use comparisons and achieve linear time. There is no hashing / excessive space / and do not use the standard algorithm of deterministic timing in time? The problem is self-locking, do I feel?

Answer 1

Hint: Take a look at Boyer and Moore's Voice Algorithm

Steps:

• Find the median of an array using the median of the median algorithm at 0 (n) time
• separation using the median pivot element
• use voice voting in each part between
  a) the middle and first element and
  b) middle and last element
• Check if the median element is required.

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

Refer to this similar publication also for additional answers.