@sachin: you can find median in linear sort.
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.
>
> 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.
