Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Wednesday, August 22, 2012
Find the minimum distance
Given an unsorted array arr[] and two numbers x and y, find the minimum
distance between x and y in arr[]. The
array might also contain duplicates. You may assume that both x and y
are different and present in arr[]
function minimumDistance (arr[],X,Y) { Lung=length(arr[]); //Lunghezza array PX=Lung; //posizione di X PY=Lung; //posizione di Y DXY=Lung; //distanza XY for(i=0, i abs(PX-PY)) DXY=abs(PX-PY); //Aggiorna la distanza minima } } return DXY; }
function minimumDistance (arr[],X,Y)
ReplyDelete{
Lung=length(arr[]); //Lunghezza array
PX=Lung; //posizione di X
PY=Lung; //posizione di Y
DXY=Lung; //distanza XY
for(i=0, i abs(PX-PY)) DXY=abs(PX-PY); //Aggiorna la distanza minima
}
}
return DXY;
}
*meglio che calcolare tutte le distanze, O(Lungh)
Just an idea:
ReplyDeleteBuild a map of positions of each unique element in arr[]:
map[a] = list of positions in arr[] where "a" appears.
This require O(n).
Then, generate all the pairs of elements from the lists map[x] and map[y]. Return the pair (a, b) where abs(a - b) - 1 is minimum.
Maybe the pair generation is not the optimum but keep the algo simple to implement :)