I saw a problem on some certain forum days ago:

Design an algorithm that, given a list of N elements in an array, finds all the elements that appear more that n/3 times in linear time and using constant space only.

Well, another constant space problem. Without this constrain, we can easily achieve an linear time algorithm by using a hashmap or just another array.

I didn't have good solutions. And then I searched online, and found that there was a particular name for this problem: Majority Vote. And there's a neat algorithm here .

While this algorithm seemed not that straightforward to me at first, the idea behind it was quite simple:

The majority ( if there exists ) will remain the same when we delete 3 different elements from list each time, taking the problem I stated at first as the example.

## No comments:

## Post a Comment