Majority Element

Posted on

Idea:

  1. Boyer-Moore Majority Vote

Time: O(n) Space: O(1)

Step 1. Iterate through the array:

if counter = 0 { current candidate = x; counter = 1}

else {

if current x = candidate {counter ++}

else {counter –}

}

Step 2. Determine if the remaining element is a valid majority element

With Step 1 candidate, iterate through array to check the occurrences.

Screen Shot 2015-10-05 at 7.04.56 PM

2. HashTable 

Time: O(n) Space: O(n)

Hash table stores the occurrence frequency of each element.

Pick out the one with frequency > [n/2]

Screen Shot 2015-10-05 at 7.21.48 PM

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s