wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find two nearest elements in Integer array
        
(Message started by: bbskill on Oct 25^th, 2007, 10:07am)

Title: Find two nearest elements in Integer array
Post by bbskill on Oct 25^th, 2007, 10:07am

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.

Title: Re: Find two nearest elements in Integer array
Post by towr on Oct 25^th, 2007, 11:30am

You could use radix sort; after that it's trivial.

Title: Re: Find two nearest elements in Integer array
Post by Aryabhatta on Oct 25^th, 2007, 11:45am

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

Title: Re: Find two nearest elements in Integer array
Post by bbskill on Oct 26^th, 2007, 3:44am

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.

Title: Re: Find two nearest elements in Integer array
Post by towr on Oct 26^th, 2007, 3:53am

on 10/26/07 at 03:44:01, 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.