Find the element with the most "neighbors" in a sequence
Posted
by Bao An
on Stack Overflow
See other posts from Stack Overflow
or by Bao An
Published on 2010-04-22T02:53:17Z
Indexed on
2010/04/22
3:13 UTC
Read the original article
Hit count: 287
algorithm
Assume that we have a sequence S with n elements <x1,x2,...,xn>. A pair of elements xi,xj are considered neighbors if |xi-xj|<d, with d a given distance between two neighbors. So how can find out the element that has most neighbors in the sequence?
(A simply way is sorting the sequence and then calculating number of each element but it's time complexity is quite large):
O(nlogn)
May you please help me find a better way to reduce time complexity?
© Stack Overflow or respective owner
