wu :: forums
« wu :: forums - Find two nearest elements in Integer array »
Welcome, Guest. Please Login or Register.
Mar 14th, 2025, 11:55am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs (Moderators: Eigenray, ThudnBlunder, SMQ, Grimbal, towr, william wu, Icarus)
   Find two nearest elements in Integer array		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Find two nearest elements in Integer array  (Read 731 times)
bbskill
Newbie
*





   


Posts: 42
Find two nearest elements in Integer array  
« on: Oct 25th, 2007, 10:07am »		 Quote Quote Modify Modify
For example,  {1, -14, 6, 13, 3, 10} return 1, 3.
Since abs(1,3) == 2 is minimum.
Does there exist an algorithm in O(n) time.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Find two nearest elements in Integer array  
« Reply #1 on: Oct 25th, 2007, 11:30am »		 Quote Quote Modify Modify
You could use radix sort; after that it's trivial.
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
Aryabhatta
Uberpuzzler
*****






   


Gender: male
 Posts: 1321
Re: Find two nearest elements in Integer array  
« Reply #2 on: Oct 25th, 2007, 11:45am »		 Quote Quote Modify Modify
If only comparisons are allowed, no O(n) algo can be given.
 
This follows from the lower bounds for the "Element Uniqueness Problem" : http://en.wikipedia.org/wiki/Element_uniqueness_problem
 
IP Logged
bbskill
Newbie
*





   


Posts: 42
Re: Find two nearest elements in Integer array  
« Reply #3 on: Oct 26th, 2007, 3:44am »		 Quote Quote Modify Modify
to towr:
Without any sort,  could we reach an O(n) time algorithm?
 
to Aryabhatta:
Why does it follow the lower bounds for the "Element Uniqueness Problem"? Could you explain it more.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Find two nearest elements in Integer array  
« Reply #4 on: Oct 26th, 2007, 3:53am »		 Quote Quote Modify Modify
on Oct 26th, 2007, 3:44am, bbskill wrote:
to towr:
Without any sort,  could we reach an O(n) time algorithm?
I doubt it very much. Radix sort is O(n) though (it can be, because it's not a comparison based sort)
 
Quote:
to Aryabhatta:
Why does it follow the lower bounds for the "Element Uniqueness Problem"? Could you explain it more.
If you can find the minimum distance in O(n), then you can find whether all elements are unique in O(n) (if the minimum distance is 0, not all elements are unique, otherwise they are).
So given that, for comparison based algorithms, O(n log n) is the best you can do on the uniqueness question, you cannot do better on finding the minimum distance.
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board