CODEWITHSUNDEEP
algorithm
Qiang Li
Qiang Li

Reputation: 10855

algorithm to find the three majority elements in an array

Let's say there are three elements in a non-sorted array all of which appear more than one-fourth times of the total number of elements.

What is the most efficient way to find these elements? Both for non-online and online versions of this question.

Thank you!

Edit

The non-online version I was referring to is: this array is specified in full. The online version means the array elements are coming one at a time.

I require the space in addition to time complexity to be tight.

disclaimer: THIS IS NOT HOMEWORK! I consider this as research-level question.

Upvotes: 8

Views: 2161

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183868

Remember up to three elements, together with counters.

  1. remember first element, set count1 = 1
  2. scan until you find first different element, increasing count1 for each occurrence of element 1
  3. remember second elemt, set count2 = 1
  4. scan until you find first element different from elem1 and elem2, incrementing count1 or count2, depending which element you see
  5. remember third element, set count3 = 1
  6. continue scanning, if the element is one of the remembered, increment its count, if it's none of the remembered, decrement all three counts; if a count drops to 0, forget the element, go to step 1, 3, or 5, depending on how many elements you forget
  7. If you have three elements occurring strictly more than one-fourth times the number of elements in the array, you will end up with three remembered elements each with positive count, these are the three majority elements.

Small constant additional space, O(n), no sorting.

Upvotes: 13

smitec
smitec

Reputation: 3049

create a histogram of the entries, sort it, and take the three largest entries.

Upvotes: 2

Related Questions