@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 <rahul23111...@gmail.com>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 <rahul23111...@gmail.com>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.
