Trova il numero più vicino in una lista di numeri

Question

Ho una lista di numeri costanti. Ho bisogno di trovare il numero più vicino a x nella lista dei numeri. Qualche idea su come implementare questo algoritmo?

Answer 1

Bene, non è possibile farlo più veloce di O(N) perché è necessario controllare tutti i numeri per essere sicuri di avere quello più vicino. Detto questo, perché non utilizzare una semplice variazione per trovare il minimo, cercando quello con la differenza assoluta minima con x?

Se si può dire che l'elenco è ordinato dall'inizio (e consente l'accesso casuale, come un array), un approccio migliore consiste nell'utilizzare una ricerca binaria. Quando si termina la ricerca all'indice i (senza trovare x), basta scegliere il meglio da quell'elemento e dai suoi vicini.

Answer 2

Esso può essere fatto utilizzando SortedList:
Blog post on finding closest number
Se la complessità che stai cercando conta solo la ricerca della complessità è O (log (n)). La costruzione della lista costerà O (n * log (n))

Se si intende inserire l'elemento nell'elenco più volte di quanto si sta per interrogarlo per il numero più vicino, la scelta migliore è quello di utilizzare List e utilizzare l'algoritmo naive per interrogarlo per il numero più vicino. Ogni ricerca avrà un costo O (n) ma il tempo di inserimento sarà ridotto a O (n).

complessità generale: Se la raccolta ha n numeri e cercato q volte -
Elenco: O(n+q*n)
elenco ordinato: O(n*log(n)+q*log(n))

significato, da qualche q la allineati la lista fornirà una migliore complessità.

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(); 
} 

Null significa che non c'era il numero più vicino. Se ci sono due numeri con la stessa differenza, sceglierà quello più vicino a zero. Se due numeri hanno la stessa distanza da zero, verrà scelto il numero positivo.

Modifica in risposta al commento di Eric:

Ecco una versione che ha la stessa semantica, ma utilizza l'operatore Min. Richiede un'implementazione di IComparable<> in modo da poter utilizzare Min mantenendo il numero associato a ciascuna distanza. Ho anche reso un metodo di estensione per facilità d'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

Suppongo che l'array non sia ordinato. In ordine può essere più veloce

Penso che il metodo più semplice e veloce sia l'utilizzo di algoritmi lineari per la ricerca di minimo o massimo, ma invece di confrontare i valori si confronta il valore assoluto della differenza tra questo e l'ago.

In C++ (non riesco a C#, ma sarà simile) può codificare simile a questa:

// 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

In generale le persone su questo sito non fare il vostro lavoro per voi. Dal momento che non hai inserito il codice, non invierò nemmeno il codice. Tuttavia, ecco un possibile approccio.

Passare attraverso l'elenco, sottraendo il numero nell'elenco da x. Prendi il valore assoluto di questa differenza e confrontalo con il miglior risultato precedente che hai ottenuto e, se la differenza attuale è inferiore al miglior risultato precedente, salva il numero corrente dalla lista. Alla fine del ciclo avrai la tua risposta.

Answer 6

essere pigro non ho controllare questo, ma non deve questo lavoro

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; 
        } 
       }