|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |