Encontrar la distancia mínima entre elementos en un arreglo.
Estoy tratando de encontrar la distancia mínima entre 2 elementos dados de un array.
por ejemplo, en el siguiente array {1,2,3,4,5,6,7} la distancia entre los elementos 3,7 es 4.
He escrito un código que calcula con éxito esa distancia, pero si hay duplicados, no funciona.
A continuación está lo que he escrito hasta ahora. ¿Qué me falta? ¿Debo agregar alguna condición?
Además, debe hacerse con una complejidad no mayor que O(n).
“`java
public static int findMinDiff(int [] a, int x, int y) {
//índice anterior y distancia mínima
int next = 0, curr = 0, min_dist = Integer.MAX_VALUE;
for(int i=0 ; i<a.length ; i++)
{
if(a[i]==x)
{
curr = i;
}
else if(a[i] == y){
next = i;
}
}
min_dist = math.abs(curr – next);
if(min_dist==integer.max_value)
return -1;
return min_dist;
}
“` ;=”” i++)=”” {=”” if(a[i]=”=x)” {=”” curr=”i;” }=”” else=”” if(a[i]=”=” y){=”” next=”i;” }=”” }=”” min_dist=”Math.abs(curr” -=”” next);=”” if(min_dist=”=Integer.MAX_VALUE)” return=”” -1;=”” return=”” min_dist;=”” }=””></a.length ; i++)
{
if(a[i]==x)
{
curr = i;
}
else if(a[i] == y){
next = i;
}
}
min_dist = math.abs(curr – next);
if(min_dist==integer.max_value)
return -1;
return min_dist;
}
“`>
davy.ai
Para manejar duplicados, debes modificar el código existente para hacer un seguimiento del índice anterior de ambos elementos por separado. Puedes usar dos variables para almacenar los índices anteriores de x e y respectivamente. Luego, debes verificar la diferencia absoluta entre el índice actual de x y el índice anterior de y, así como la diferencia absoluta entre el índice actual de y y el índice anterior de x. Necesitas retornar el mínimo de estas dos distancias como la distancia mínima entre los dos elementos.
este fragmento de código mantiene dos punteros que representan los índices anteriores de x e y mientras se itera a través del arreglo. cuando se encuentra x, se calcula la distancia absoluta entre su ubicación actual y el índice anterior de y, y se compara con la distancia mínima existente. de manera similar, cuando se encuentra el elemento y, se calcula la distancia absoluta entre su ubicación actual y el índice anterior de x, y se compara con la distancia mínima. finalmente, la distancia mínima se devuelve como resultado.
la complejidad temporal de este algoritmo es o(n), que está dentro del límite deseado. ;=”” i++)=”” {=”” if(a[i]=”=x)” {=”” if(prevy=”” !=”-1)” min_dist=”Math.min(min_dist,” i=”” -=”” prevy);=”” prevx=”i;” }=”” else=”” if(a[i]=”=” y){=”” if(prevx=”” !=”-1)” min_dist=”Math.min(min_dist,” i=”” -=”” prevx);=”” prevy=”i;” }=”” }=”” if(min_dist=”=Integer.MAX_VALUE)” return=”” -1;=”” return=”” min_dist;=”” }=”” “`=”” este=”” fragmento=”” de=”” código=”” mantiene=”” dos=”” punteros=”” que=”” representan=”” los=”” índices=”” anteriores=”” de=”” x=”” e=”” y=”” mientras=”” se=”” itera=”” a=”” través=”” del=”” arreglo.=”” cuando=”” se=”” encuentra=”” x,=”” se=”” calcula=”” la=”” distancia=”” absoluta=”” entre=”” su=”” ubicación=”” actual=”” y=”” el=”” índice=”” anterior=”” de=”” y,=”” y=”” se=”” compara=”” con=”” la=”” distancia=”” mínima=”” existente.=”” de=”” manera=”” similar,=”” cuando=”” se=”” encuentra=”” el=”” elemento=”” y,=”” se=”” calcula=”” la=”” distancia=”” absoluta=”” entre=”” su=”” ubicación=”” actual=”” y=”” el=”” índice=”” anterior=”” de=”” x,=”” y=”” se=”” compara=”” con=”” la=”” distancia=”” mínima.=”” finalmente,=”” la=”” distancia=”” mínima=”” se=”” devuelve=”” como=”” resultado.=”” la=”” complejidad=”” temporal=”” de=”” este=”” algoritmo=”” es=”” o(n),=”” que=”” está=”” dentro=”” del=”” límite=””></a.length ; i++)
{
if(a[i]==x)
{
if(prevy != -1)
min_dist = math.min(min_dist, i – prevy);
prevx = i;
}
else if(a[i] == y){
if(prevx != -1)
min_dist = math.min(min_dist, i – prevx);
prevy = i;
}
}
}
“`
este fragmento de código mantiene dos punteros que representan los índices anteriores de x e y mientras se itera a través del arreglo. cuando se encuentra x, se calcula la distancia absoluta entre su ubicación actual y el índice anterior de y, y se compara con la distancia mínima existente. de manera similar, cuando se encuentra el elemento y, se calcula la distancia absoluta entre su ubicación actual y el índice anterior de x, y se compara con la distancia mínima. finalmente, la distancia mínima se devuelve como resultado.
la complejidad temporal de este algoritmo es o(n), que está dentro del límite deseado.>