@Aditya: Heapifying is an O(n log n) operation.
Instead, use a radix sort, which is O(n). Since the data are real
numbers (I'll assume of type double), some trickiness is required to
apply the radix sort to them. The overall idea is to complement the
sign bit (negate the numbers) and then treat them as unsigned 64-bit
integers. Perform the radix sort on the array of unsigned integers
using any radix you choose. E.g., if you choose radix 256, then eight
passes are required. Afterwards, recomplement the sign bit. All of
this can be done in O(n). Now it is easy to find the largest adjacent
differences. Total algorithm is O(n).
I'm not saying that this is the best way to solve the problem.
Heapifying or an O(n log n) sort might be faster than the radix sort
on practical-sized problems. But this algorithm does meet the
problem's stated requirements.
Dave
On Aug 6, 8:10 am, aditya bindal <adityabindal1...@gmail.com> wrote:
> i feel do a heapify and then just try an O(n) adjacent element difference on
> the resulting one.
>
>
>
> On Sat, Aug 6, 2011 at 6:34 PM, Algo Lover <algolear...@gmail.com> wrote:
> > given an UNSORTED real number array x1,x2,...,xn, how to find the max
> > distance of two neighbouring numbers in the number axis. Is there any
> > method with O(n) time complexity?
> > see an example
> > given x[]={2.0,1.0,9.0,-3.5}
> > then the answer is 7.0, because on the number axis, it is
> > -3.5,1.0,2.0,9.0 from left to right.
> > distance between two neighbouring numbers are 1-(-3.5),2-1,9-2.
> > so the answer is 9-2=7
>
> > --
> > 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.- Hide quoted text -
>
> - Show quoted text -
--
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.
