can some body please explain voting algo to me . On Wed, Jul 11, 2012 at 12:42 PM, Navin Kumar <[email protected]>wrote:
> @sachin: > > > http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html > > On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal > <[email protected]>wrote: > >> To Mr. B >> how will you find median in O(n) time? please elaborate. >> >> >> On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: >>> >>> I found a similar solution looking somewhere else. >>> >>> The solution for this problem is: >>> a. There can be atmost 3 elements (only 3 distinct elements with each >>> repeating n/3 times) -- check for this and done. -- O(n) time. >>> b. There can be atmost 2 elements if not above case. >>> >>> 1. Find the median of the input. O(N) >>> 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark >>> for output if yes}* >>> 3. partition the array based on median found above. - O(n) -- >>> {partition is single step in quicksort} >>> 4. find median in left partition from (3). - O(n) >>> 5. check if median element is repeared n/3 times or more - O(n) *{mark >>> for output if yes}* >>> 6. find median in right partition from (3). - O(n) >>> 7. check if median element is repeared n/3 times or more - O(n) *{mark >>> for output if yes}* >>> >>> its 7*O(N) => O(N) solution. Constant space. >>> >>> we need not check further down or recursively. {why? reason it.. its >>> simple} >>> >>> >>> On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: >>>> >>>> >>>> Design an algorithm that, given a list of n elements in an array, finds >>>> all the elements that appear more than n/3 times in the list. The algorithm >>>> should run in linear time >>>> >>>> ( n >=0 ). >>>> >>>> You are expected to use comparisons and achieve linear time. No >>>> hashing/excessive space/ and don't use standard linear time deterministic >>>> selection algo. >>>> >>>> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ. >> >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
