Ho una matrice che memorizza un insieme di coordinate x positive in modo ordinato,
dì arr={1, 4, 5, 9, 12, 45}
ecc.
E ho una distanza massima k
che posso passare da un punto all'altro di un altro punto, lasciare k=3
.
Ora, dati due punti x
e y(arr[x]<arr[y])
ho bisogno di determinare se posso raggiungere da x
a y
. Potrò raggiungere y
da x
se la distanza tra ogni due hop è inferiore o uguale a k
.
Qui supponiamo x=1 y=4
quindi posso passare da 1 & 2 2 quindi 2 & 3 3, ma poiché la distanza tra 3 e 4 è maggiore di 3 non posso andare così in questo caso non posso raggiungere.
Ma se x=1
e y=2
allora posso raggiungere.
Può essere semplicemente risolto con O (n). Ho creato un ciclo for da arr[x]
a arr[y]
e per ogni coppia di punti controllo se la distanza tra loro è minore o uguale a k
.
Ma voglio un algoritmo migliore. Sto pensando di fare qualcosa come la ricerca binaria. Qualcuno può suggerire un buon algoritmo?