I think it can be done by using some randomized algorithm. Divide the array into subarrays of equal size and then pick a random element from each group.Do it 3-4 times,if random number comes out equal for most of the times,return that element. I haven't tried it.
On Fri, Jul 13, 2012 at 10:53 AM, Ganesh M <ganesh.muniya...@gmail.com>wrote: > I guess the > link<http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html>talks > about modified quick sort approach. Remember, if your choise of pivot > is bad everytime, this will have a worst case performance of O(n). You > should refer to Selection > Algorithm<http://en.wikipedia.org/wiki/Selection_algorithm>for better worst > case performance. > > On Wednesday, July 11, 2012 3:12:07 PM UTC+8, Navin Kumar wrote: > >> @sachin: >> >> http://valis.cs.uiuc.edu/~**sariel/research/CG/applets/** >> linear_prog/median.html<http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html> >> >> On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal <sachingoyal....@gmail.com >> > 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<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+unsubscribe@** >>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>> For more options, visit this group at http://groups.google.com/** >>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>> >> >> -- > 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/-/lZKI47459WgJ. > > 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. > -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- 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.
