Encontrar el número más cercano en una matriz

Question

¿En una matriz primero tenemos que encontrar si existe un número deseado en eso o no? Si no, ¿cómo encontraré un número más cercano al número deseado en Java?

Answer 1

Array.indexOf() para averiguar si el elemento existe o no. Si no lo hace, itere sobre una matriz y mantenga una variable que contenga el valor absoluto de la diferencia entre el elemento deseado y i -th. Elemento de retorno con la mínima diferencia absoluta.

complejidad global es O (2n), que puede ser reducido aún más a una sola iteración sobre una matriz (que habría O (n)). Sin embargo, no hará mucha diferencia.

Answer 2

Una idea:

int nearest = -1; 
int bestDistanceFoundYet = Integer.MAX_INTEGER; 
// We iterate on the array... 
for (int i = 0; i < array.length; i++) { 
    // if we found the desired number, we return it. 
    if (array[i] == desiredNumber) { 
    return array[i]; 
    } else { 
    // else, we consider the difference between the desired number and the current number in the array. 
    int d = Math.abs(desiredNumber - array[i]); 
    if (d < bestDistanceFoundYet) { 
     // For the moment, this value is the nearest to the desired number... 
     bestDistanceFoundYet = d; // Assign new best distance... 
     nearest = array[i]; 
    } 
    } 
} 
return nearest; 

Answer 3

Si se ordena la matriz, y luego hacer una búsqueda binaria modificada. Básicamente, si no encuentras el número, al final de la búsqueda devuelve el límite inferior.

Answer 4

Lo único que falta es la semántica del más cercano.

¿Qué haces si estás buscando seis y tu matriz tiene cuatro y ocho?

¿Cuál es el más cercano?

Answer 5

Pseudocódigo para devolver la lista de los enteros más cercanos.

myList = new ArrayList();   

if(array.length==0) return myList; 

myList.add(array[0]); 

int closestDifference = abs(array[0]-numberToFind); 

for (int i = 1; i < array.length; i++) { 

int currentDifference= abs(array[i]-numberToFind); 

    if (currentDifference < closestDifference) { 

    myList.clear(); 

    myList.add(array[i]); 

     closestDifference = currentDifference; 

    } else { 

    if(currentDifference==closestDifference) { 

     if(myList.get(0) !=array[i]) && (myList.size() < 2) { 

      myList.add(array[i]); 

     } 
      } 

     } 

} 

return myList; 

Answer 6

Otra definición común de "más cercano" se basa en el cuadrado de la diferencia. El esquema es similar a la proporcionada por romaintaz, excepto que desea calcular

long d = ((long)desiredNumber - array[i]); 

y luego comparar (d * d) a la distancia más cercana.

Notaque yo haya escrito d como long en lugar de int Para evitar el desbordamiento, lo que puede ocurrir incluso con el cálculo basado en valor absoluto. (Por ejemplo, piense en lo que sucede cuando desiredValue es al menos la mitad del valor máximo de 32 bits firmado, y la matriz contiene un valor con la magnitud correspondiente pero signo negativo.)

Finalmente, escribo el método para devolver el índice del valor ubicado, en lugar del valor en sí mismo. En cualquiera de estos dos casos:

• cuando la matriz tiene una longitud de cero, y
• si se agrega un parámetro "tolerancia" que limita la diferencia máxima que se considere como un partido,

puede usar -1 como un valor fuera de banda similar a la especificación en indexOf.

Answer 7

int d = Math.abs(desiredNumber - array[i]); 
    if (d < bestDistanceFoundYet) { 
     // For the moment, this value is the nearest to the desired number... 
     nearest = array[i]; 
    } 

De esta manera se encuentran el último número más cercano a número deseado debido bestDistanceFoundYet es constante y d memorizar el último valor de la PAsigne si (d < ...).

Si desea encontrar el número más cercano CON CUALQUIER DISTANCIA para el número deseado (d no importa), puede memorizar el último valor posible. En el caso de que pueda probar

if(d<last_d_memorized){ //the actual distance is shorter than the previous 
    // For the moment, this value is the nearest to the desired number... 
      nearest = array[i]; 
    d_last_memorized=d;//is the actual shortest found delta 
} 

Answer 8

int[] somenumbers = getAnArrayOfSomenumbers(); 
int numbertoLookFor = getTheNumberToLookFor(); 

boolean arrayContainsNumber = 
    new HashSet(Arrays.asList(somenumbers)) 
     .contains(numbertoLookfor); 

Es rápido, también.

Oh, ¿deseaba encontrar el número más cercano? En ese caso:

int[] somenumbers = getAnArrayOfSomenumbers(); 
int numbertoLookFor = getTheNumberToLookFor(); 

ArrayList<Integer> l = new ArrayList<Integer>(
    Arrays.asList(somenumbers) 
); 
Collections.sort(l); 
while(l.size()>1) { 
    if(numbertoolookfor <= l.get((l.size()/2)-1)) { 
    l = l.subList(0, l.size()/2); 
    } 
    else { 
    l = l.subList(l.size()/2, l.size); 
    } 
} 

System.out.println("nearest number is" + l.get(0)); 

Oh, espera: ¿estabas buscando una solución por mínimos cuadrados?

Collections.sort(l, new Comparator<Integer>(){ 
    public int compare(Integer o1, Integer o2) { 
    return (o1-numbertoLookFor)*(o1-numbertoLookFor) - 
      (o2-numbertoLookFor)*(o2-numbertoLookFor); 
    }}); 

System.out.println("nearest number is" + l.get(0)); 

Answer 9

Algunas cosas a señalar:

1 - Se puede convertir la matriz a una lista utilizando

Arrays.asList(yourIntegerArray); 

2 - El uso de una lista, puede simplemente usar indexOf().

3 - Considere un escenario en el que tiene una lista de cierta longitud, desea el número más cercano a 3, ya ha encontrado que 2 está en la matriz, y sabe que 3 no lo está. Sin consultar los otros números, puede concluir con seguridad que 2 es el mejor, porque es imposible estar más cerca. Sin embargo, no estoy seguro de cómo funciona indexOf(), por lo que puede que esto no te acelere.

4 - Expandiendo el 3, digamos que indexOf() no lleva más tiempo que obtener el valor en un índice. Entonces, si quiere el número más cercano a 3 en una matriz y ya ha encontrado 1, y tiene muchos más números para verificar, entonces será más rápido simplemente verificar si 2 o 4 están en la matriz.

5 - Ampliando en 3 y 4, creo que sería posible aplicar esto a carrozas y dobles, aunque requeriría que use un tamaño de paso menor que 1 ... calcular qué tan pequeño parece más allá del alcance de la pregunta, sin embargo.

Answer 10

// paulmurray's answer to your question is really the best : 

// The least square solution is way more elegant, 
// here is a test code where numbertoLookFor 
// is zero, if you want to try ... 

import java.util.* ; 

public class main { 
    public static void main(String[] args) 
    { 
     int[] somenumbers = {-2,3,6,1,5,5,-1} ; 
     ArrayList<Integer> l = new ArrayList<Integer>(10) ; 
     for(int i=0 ; i<somenumbers.length ; i++) 
     { 
      l.add(somenumbers[i]) ; 
     } 
     Collections.sort(l, 
       new java.util.Comparator<Integer>() 
       { 
        public int compare(Integer n1, Integer n2) 
        { 
         return n1*n1 - n2*n2 ; 
        } 
       } 
     ) ; 
     Integer first = l.get(0) ; 
     System.out.println("nearest number is " + first) ; 
    } 
} 

Answer 11

// Esto funcionará

public int nearest(int of, List<Integer> in) 
{ 
int min = Integer.MAX_VALUE; 
int closest = of; 

for (int v : in) 
{ 
    final int diff = Math.abs(v - of); 

    if (diff < min) 
    { 
     min = diff; 
     closest = v; 
    } 
} 
return closest; 
}