I blog about development using .net, C#, SQL, Windows RT, and other Microsoft technologies.
Disclaimer: All posts are provided "AS IS" with no warranties, confering no rights, and expressing only my personal opinion, not Microsoft's.
Selection algorithms are very useful in many instances, like finding the majority. Given an array of size n that contains a majority item (an item that's repeated more than n/2 times), we can find that item in O(n). Basically, we can consider it as a voting process, each occurrence is a vote and each item is a candidate. Since there's a constant pool of votes, each candidate is winning a vote when it appears and losing a vote when another candidate is appearing instead. If the number of votes becomes 0, then it's time to pick another candidate. The candidate with a positive number of votes is the majority. Using this algorithm doesn't require extra storage like a hash to store the frequency of each item, we just need an integer for storing the frequency and a variable to store the candidate. Here's a sample in C# that prints the majority in an array of integers:
No way it works, sorry.
Please consider input: 1,1,1,2,2,3,4,5,6,7 - majority is of course 1, but your alg gives response 7
No, majority is defined as the item that appears more than n/2 times.
What you do describe above is called Plurality
Agree but then the algorithm should answer "There is no majority here", i.e. it needs a little modification in the last statement:
if( frequency > 0 )
Console.WriteLine( "Majority: " + candidate );
Console.WriteLine( "There is no majority here." );
Actually, it's given that there exist such an item. There's a problem with the check you added that it may give you a false positive.