Selection of Majority in O(n)

Selection of Majority in O(n)

  • Comments 4

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:

using System;

namespace ConsoleApplication1
{
   
class Program
   
{
       
static void Main(string[] args)
       
{
           
int[] array = new int[] { 2, 1, 5, 1, 7, 1, 9, 1 };
           
int candidate = array[0], freq = 1;

           
for (int i = 1; i < array.Length; ++i)
           
{
               
freq += (candidate == array[i] ? 1 : -1);

               
if (freq == 0)
               
{
                   
candidate = array[i];
                   
freq = 1;
               
}
           
}

           
Console.WriteLine("Majority: " + candidate);
       
}
   
}
}
Leave a Comment
  • Please add 8 and 7 and type the answer here:
  • Post
  • 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.

    http://en.wikipedia.org/wiki/Majority

    What you do describe above is called Plurality

    http://en.wikipedia.org/wiki/Plurality_(voting)

  • 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 );

    else

    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.

Page 1 of 1 (4 items)