Encuentra el número más cercano en una lista de números

Question

Tengo una lista de números constantes. Necesito encontrar el número más cercano a x en la lista de los números. ¿Alguna idea sobre cómo implementar este algoritmo?

Answer 1

Bueno, no puedes hacer esto más rápido que O(N) porque tienes que verificar todos los números para asegurarte de que tienes el más cercano. Dicho esto, ¿por qué no utilizar una variación simple para encontrar el mínimo, buscando el que tenga la diferencia absoluta mínima con x?

Si puede decir que la lista está ordenada desde el principio (y permite el acceso aleatorio, como una matriz), entonces un mejor enfoque es usar una búsqueda binaria. Cuando termine la búsqueda en el índice i (sin encontrar x), solo elija lo mejor de ese elemento y sus vecinos.

Answer 2

Se puede hacer uso de SortedList:
Blog post on finding closest number
Si la complejidad que estás buscando sólo cuenta la búsqueda de la complejidad es O (log (n)). El edificio de la lista costará O (n * log (n))

Si va a insertar un elemento en la lista muchas veces más de lo que va a consultarlo para el número más cercano, entonces la mejor opción es usar List y usar un algoritmo ingenuo para consultar el número más cercano. Cada búsqueda costará O (n) pero el tiempo de inserción se reducirá a O (n).

complejidad general: Si la colección tiene n números y buscó q veces -
Lista: O(n+q*n)
lista ordenada: O(n*log(n)+q*log(n))

Significado, de alguna q del ordenadas lista proporcionará una mejor complejidad.

Answer 3

private int? FindClosest(IEnumerable<int> numbers, int x) 
{ 
    return 
     (from number in numbers 
     let difference = Math.Abs(number - x) 
     orderby difference, Math.Abs(number), number descending 
     select (int?) number) 
     .FirstOrDefault(); 
} 

Nulo significa que no había un número más cercano. Si hay dos números con la misma diferencia, elegirá el más cercano a cero. Si dos números están a la misma distancia de cero, se elegirá el número positivo.

Editar en respuesta al comentario de Eric:

Aquí está una versión que tiene la misma semántica, sino que utiliza el operador Min. Requiere una implementación de IComparable<> para que podamos usar Min mientras conservamos el número que va con cada distancia. También lo hice un método de extensión para facilidad de uso:

public static int? FindClosestTo(this IEnumerable<int> numbers, int targetNumber) 
{ 
    var minimumDistance = numbers 
     .Select(number => new NumberDistance(targetNumber, number)) 
     .Min(); 

    return minimumDistance == null ? (int?) null : minimumDistance.Number; 
} 

private class NumberDistance : IComparable<NumberDistance> 
{ 
    internal NumberDistance(int targetNumber, int number) 
    { 
     this.Number = number; 
     this.Distance = Math.Abs(targetNumber - number); 
    } 

    internal int Number { get; private set; } 

    internal int Distance { get; private set; } 

    public int CompareTo(NumberDistance other) 
    { 
     var comparison = this.Distance.CompareTo(other.Distance); 

     if(comparison == 0) 
     { 
      // When they have the same distance, pick the number closest to zero 
      comparison = Math.Abs(this.Number).CompareTo(Math.Abs(other.Number)); 

      if(comparison == 0) 
      { 
       // When they are the same distance from zero, pick the positive number 
       comparison = this.Number.CompareTo(other.Number); 
      } 
     } 

     return comparison; 
    } 
} 

Answer 4

Supongo que la matriz está desordenada. En orden puede ser más rápido

Creo que el método más simple y más rápido es usar algoritmo lineal para encontrar el mínimo o el máximo, pero en lugar de comparar valores, comparará el valor absoluto de la diferencia entre esto y la aguja.

En el C++ (no puedo C#, pero será similar) puede codificar el siguiente aspecto:

// array of numbers is haystack 
// length is length of array 
// needle is number which you are looking for (or compare with) 

int closest = haystack[0]; 
for (int i = 0; i < length; ++i) { 
    if (abs(haystack[ i ] - needle) < abs(closest - needle)) closest = haystack[i]; 
} 
return closest; 

Answer 5

En general la gente en este sitio no va a hacer su tarea para usted. Como no has publicado el código, tampoco publicaré el código. Sin embargo, aquí hay un posible enfoque.

Pasa por la lista, restando el número de la lista de x. Tome el valor absoluto de esta diferencia y compárela con el mejor resultado anterior que haya obtenido y, si la diferencia actual es menor que el mejor resultado anterior, guarde el número actual de la lista. Al final del ciclo tendrás tu respuesta.

Answer 6

ser perezoso no he comprobar esto, pero no debe este trabajo

private int FindClosest(IEnumerable<int> numbers, int x) 
{ 
    return 
     numbers.Aggregate((r,n) => Math.Abs(r-x) > Math.Abs(n-x) ? n 
           : Math.Abs(r-x) < Math.Abs(n-x) ? r 
           : r < x ? n : r); 
} 

Answer 7

Haskell:

import Data.List (minimumBy) 
import Data.Ord (comparing) 

findClosest :: (Num a, Ord a) => a -> [a] -> Maybe a 
findClosest _ [] = Nothing 
findClosest n xs = Just $ minimumBy (comparing $ abs . (+ n)) xs 

Answer 8

   Performance wise custom code will be more use full. 

       List<int> results; 
       int targetNumber = 0; 
       int nearestValue=0; 
       if (results.Any(ab => ab == targetNumber)) 
       { 
        nearestValue= results.FirstOrDefault<int>(i => i == targetNumber); 
       } 
       else 
       { 
        int greaterThanTarget = 0; 
        int lessThanTarget = 0; 
        if (results.Any(ab => ab > targetNumber)) 
        { 
         greaterThanTarget = results.Where<int>(i => i > targetNumber).Min(); 
        } 
        if (results.Any(ab => ab < targetNumber)) 
        { 
         lessThanTarget = results.Where<int>(i => i < targetNumber).Max(); 
        } 

        if (lessThanTarget == 0) 
        { 
         nearestValue= greaterThanTarget; 
        } 
        else if (greaterThanTarget == 0) 
        { 
         nearestValue= lessThanTarget; 
        } 
        else if (targetNumber - lessThanTarget < greaterThanTarget - targetNumber) 
        { 
         nearestValue= lessThanTarget; 
        } 
        else 
        { 
          nearestValue= greaterThanTarget; 
        } 
       }