Find the element with the most "neighbors" in a sequence
- by Bao An
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?