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 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.