@rahul, the voting algorithm may not give the majorty element in the array
if the majorty element occurs <=n/2 times.
but the problem clearly says that "majorty element that appears more than
n/2 times".
in such cases, the voting algo always gives the corret majorty element, if
exists.
On Sun, Mar 11, 2012 at 12:55 PM, rahul sharma wrote:
> can be done easily with hashing..btu takes extra space.
> cant we simplify just by one step.
>
>
> On Sun, Mar 11, 2012 at 12:46 PM, rahul sharma wrote:
>
>> *refered from:-http://www.geeksforgeeks.org/archives/503
>>
>> basically want to know that whether voting algo is corret???
>> *2,2,2,3,3,4,4
>> in this case it is giving majority element as 4 but it should be 3???plz
>> explain.
>> *
>> METHOD 3 (Using Moore’s Voting Algorithm)*
>>
>> This is a two step process.
>> 1. Get an element occurring most of the time in the array. This phase
>> will make sure that if there is a majority element then it will return that
>> only.
>> 2. Check if the element obtained from above step is majority element.
>>
>> *1. Finding a Candidate:*
>> The algorithm for first phase that works in O(n) is known as Moore’s
>> Voting Algorithm. Basic idea of the algorithm is if we cancel out each
>> occurrence of an element e with all the other elements that are different
>> from e then e will exist till end if it is a majority element.
>>
>> findCandidate(a[], size)
>> 1. Initialize index and count of majority element
>> maj_index = 0, count = 1
>> 2. Loop for i = 1 to size – 1
>> (a)If a[maj_index] == a[i]
>> count++
>> (b)Else
>> count--;
>> (c)If count == 0
>> maj_index = i;
>> count = 1
>> 3. Return a[maj_index]
>>
>> Above algorithm loops through each element and maintains a count of
>> a[maj_index], If next element is same then increments the count, if next
>> element is not same then decrements the count, and if the count reaches 0
>> then changes the maj_index to the current element and sets count to 1.
>> First Phase algorithm gives us a candidate element. In second phase we
>> need to check if the candidate is really a majority element. Second phase
>> is simple and can be easily done in O(n). We just need to check if count of
>> the candidate element is greater than n/2.
>>
>> Example:
>> A[] = 2, 2, 3, 5, 2, 2, 6
>> Initialize:
>> maj_index = 0, count = 1 –> candidate ‘2?
>> 2, 2, 3, 5, 2, 2, 6
>>
>> Same as a[maj_index] => count = 2
>> 2, 2, 3, 5, 2, 2, 6
>>
>> Different from a[maj_index] => count = 1
>> 2, 2, 3, 5, 2, 2, 6
>>
>> Different from a[maj_index] => count = 0
>> Since count = 0, change candidate for majority element to 5 => maj_index
>> = 3, count = 1
>> 2, 2, 3, 5, 2, 2, 6
>>
>> Different from a[maj_index] => count = 0
>> Since count = 0, change candidate for majority element to 2 => maj_index
>> = 4
>> 2, 2, 3, 5, 2, 2, 6
>>
>> Same as a[maj_index] => count = 2
>> 2, 2, 3, 5, 2, 2, 6
>>
>> Different from a[maj_index] => count = 1
>>
>> Finally candidate for majority element is 2.
>>
>> First step uses Moore’s Voting Algorithm to get a candidate for majority
>> element.
>>
>> 2.* Check if the element obtained in step 1 is majority*
>>
>> printMajority (a[], size)
>> 1. Find the candidate for majority
>> 2. If candidate is majority. i.e., appears more than n/2 times.
>>Print the candidate
>> 3. Else
>>Print "NONE"
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
