http://blogs.msdn.com/b/mohamedg/archive/2009/08/16/selection-of-majority-in-o-n.aspxSelection 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 aen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)http://blogs.msdn.com/b/mohamedg/archive/2009/08/16/selection-of-majority-in-o-n.aspx#9872736Mon, 17 Aug 2009 22:37:54 GMT91d46819-8472-40ad-a661-2c78acb4018c:9872736Mohamed Mahmoud El-Geish<p>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.</p> <div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9872736" width="1" height="1">http://blogs.msdn.com/b/mohamedg/archive/2009/08/16/selection-of-majority-in-o-n.aspx#9872223Mon, 17 Aug 2009 14:34:56 GMT91d46819-8472-40ad-a661-2c78acb4018c:9872223Val<p>Agree but then the algorithm should answer &quot;There is no majority here&quot;, i.e. it needs a little modification in the last statement:</p> <p>if( frequency &gt; 0 )</p> <p> Console.WriteLine( &quot;Majority: &quot; + candidate );</p> <p>else</p> <p> Console.WriteLine( &quot;There is no majority here.&quot; );</p> <div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9872223" width="1" height="1">http://blogs.msdn.com/b/mohamedg/archive/2009/08/16/selection-of-majority-in-o-n.aspx#9871796Sun, 16 Aug 2009 23:42:20 GMT91d46819-8472-40ad-a661-2c78acb4018c:9871796Mohamed Mahmoud El-Geish<p>No, majority is defined as the item that appears more than n/2 times.</p> <p><a rel="nofollow" target="_new" href="http://en.wikipedia.org/wiki/Majority">http://en.wikipedia.org/wiki/Majority</a></p> <p>What you do describe above is called Plurality</p> <p><a rel="nofollow" target="_new" href="http://en.wikipedia.org/wiki/Plurality_">http://en.wikipedia.org/wiki/Plurality_</a>(voting) </p> <div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9871796" width="1" height="1">http://blogs.msdn.com/b/mohamedg/archive/2009/08/16/selection-of-majority-in-o-n.aspx#9871749Sun, 16 Aug 2009 21:09:47 GMT91d46819-8472-40ad-a661-2c78acb4018c:9871749Zbyszek Swirski<p>No way it works, sorry.</p> <p>Please consider input: 1,1,1,2,2,3,4,5,6,7 - majority is of course 1, but your alg gives response 7</p> <div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9871749" width="1" height="1">