J'ai une liste de nombres constants. J'ai besoin de trouver le numéro le plus proche de X dans la liste des chiffres. Des idées sur la manière de mettre en œuvre cet algorithme?
8 Réponses :
Eh bien, vous ne pouvez pas faire cela plus rapidement que Si vous pouvez dire que la liste est commandée à partir du début (et permet d'accéder au hasard, comme une matrice), une meilleure approche consiste à utiliser une recherche binaire. Lorsque vous terminez la recherche à l'index i (sans trouver x ), choisissez simplement le meilleur de cet élément et ses voisins. O (n) car vous devez vérifier tous les numéros pour être sûr que vous avez le plus proche. Cela dit, pourquoi ne pas utiliser une simple variation de la recherche du minimum, à la recherche de celle avec la différence absolue minimale avec x ?
Vous pouvez battre O (n) si votre espace de recherche est trié.
Ouais, à l'aide de la logique d'arborescence de recherche binaire devrait vous laisser le faire dans O (log n).
Ou une recherche d'interpolation, O (journal journal n) moyen
Peut-être que je manque quelque chose, mais vous ne pouvez pas simplement faire une liste d'absolus numéros abs (YourNum - aiguille), faites-le sur un tableau, puis trier? Le premier index devrait être le plus proche?
@mardala c'est O (n log n) en raison du tri.
Il peut être fait en utilisant TritedList : de Si vous allez insérer un élément à la liste beaucoup plus de fois que vous allez la questionner pour le numéro le plus proche, le meilleur choix est d'utiliser Liste et utilisez naïf algorithme pour la questionner pour le nombre le plus proche. Chaque recherche coûtera o (n) mais le temps d'insérer sera réduit à o (n) . .
Complexité générale: Si la collection a n numéros et recherché q temps - Signification, de certains q la liste triée offrira une meilleure complexité.
Publier du blog sur la recherche du numéro le plus proche de
Si la complexité que vous recherchez ne comporte que la recherche de la complexité est o (journal (n)) . Le bâtiment de la liste coûtera o (n * journal (n))
Liste : O (n + q * n)
Liste triée : O (n * journal (n) + q * journal (n))
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;
}
}
Une utilisation charmante de Linq. Cependant, je notez que c'est O (n LG N) dans le temps et l'O (n) dans un espace supplémentaire. Vous pouvez le faire dans O (N) Heure et O (1) Espace si vous utilisez l'opérateur de séquence min plutôt que du tri.
En outre, vous n'avez toujours pas totalement désambigué la déclaration du problème. Et s'il y a deux chiffres avec la même différence et les deux sont également proches de zéro?
Bon point. J'ai commandé par Number décroissant pour que le nombre positif sera choisi (en l'absence d'une exigence comportementale, c'est la décision la plus raisonnable). Je travaillerai sur la solution min . Merci pour vos commentaires Eric!
Soigné. Typo mineur: numéros.sélectionnez (numéro => Nouvelle numéroDistance (x, numéro) doit être numéros.sélectionnez (numéro => Nouveau numéroDistance (TargeNumber, numéro) ne devrait-il pas?
@Johnkaster: Vous êtes correct. N'hésitez pas à éditer, sinon je le ferai.
@Bryanwatts juste fait, merci. Je voulais m'assurer que je ne marchais pas sur vos orteils. :)
@Johnkaster: a vu votre édition a été rejeté - je l'ai fait moi-même. Merci pour la suggestion.
Je suppose que le tableau est sans ordonnance. En ordre, il peut être plus rapide
Je pense que la méthode la plus simple et la plus rapide utilise l'algorithme linéaire pour la recherche minimale ou maximale, mais au lieu de comparer des valeurs, vous comparez la valeur absolue de la différence entre cette aiguille.
Dans le C ++ (je ne peux pas c # mais ce sera similaire) Code peut ressembler à ceci:
"Aiguille" est-elle une nomenclature spéciale que je ne suis pas au courant?
"aiguille dans la foin": D
"Aiguille" et "Haystack" sont des expressions souvent utilisées avec des algorithmes de recherche.
Bien que nous utilisions souvent l'expression "aiguille dans une foin" lorsque nous ne nous attendons pas à avoir de la chance de trouver l'aiguille!
@ R.martinhofernandes a fait ma journée :)
En général, les personnes sur ce site ne feront pas vos devoirs pour vous. Puisque vous n'avez pas publié le code, je ne posterai pas le code non plus. Cependant, voici une approche possible.
boucle via la liste, soustrayez le numéro dans la liste de X. Prenez la valeur absolue de cette différence et comparez-la au meilleur résultat précédent que vous avez obtenu et, si la différence actuelle est inférieure au résultat précédent, enregistrez le numéro actuel de la liste. À la fin de la boucle, vous aurez votre réponse.
L'OP a utilisé l'étiquette devoirs . Il n'essaie pas de tirer un rapide sur vous.
Être paresseux, je n'ai pas vérifié cela mais ne devrait pas ce travail
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);
}
haskell:
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;
}
}
N'oubliez pas d'envisager les cas inhabituels. (1) Et s'il n'y a pas de nombre le plus proche? et (2) Et s'il existe deux numéros les plus proches différents?