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.
