Warp wrote:
>   Yes, you obviously require a pointer to the first and last nodes,

Cool. It was obvious to me, but I thought maybe smarter folks had come 
up with something less obvious. ;-)

I had an interesting question today:

Given a large number N of points (say, millions) in a 2D cartesian 
space, how do you find the K points closest to the origin most 
efficiently?  E.g., you have a million (X,Y) pairs in an unsorted array; 
how do you find the five thousand pairs with the smallest (X*X+Y*Y) values?

You can actually do it with better time than "sort the whole list and 
pick the five thousand first elements". Not, AFAIK, better in the O() 
sense, but you can cut out a lot of unnecessary computation.

-- 
Darren New / San Diego, CA, USA (PST)
  Helpful housekeeping hints:
   Check your feather pillows for holes
    before putting them in the washing machine.

Post a reply to this message