查找数字列表中最接近的数字

Question

我有一个常数的列表。我需要在数字列表中找到最接近x的数字。关于如何实现这个算法的任何想法？

Answer 1

那么，你不能这样做比O(N)快，因为你必须检查所有的数字，以确保你有最接近的。这就是说，为什么不使用简单的变化来找到最小值，寻找一个与最小绝对差值的变量，它与x？

如果你可以说列表是从头开始排序的（它允许随机访问，就像数组一样），那么更好的方法是使用二分搜索。当您在索引i（没有找到x）时结束搜索时，只需从该元素及其邻居中选择最佳元素即可。

Answer 2

它可以通过SortedList做到：
Blog post on finding closest number
如果你正在寻找数只有搜索的复杂性是O（日志（n））的复杂性。列表建设将花费O（n * log（n））

如果您要将项目插入列表的次数比您要查询最接近的数字多得多，那么最佳选择是使用List并使用朴素算法来查询最近的数字。每个搜索将花费O（n），但插入的时间将减少到O（n）。

一般的复杂性：如果集合有ñ号和搜索q倍 -
列表：O(n+q*n)
排序清单：O(n*log(n)+q*log(n))

意义，从一些q排序列表将提供更好的复杂性。

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表示没有最接近的数字。如果有两个具有相同差异的数字，它将选择最接近于零的数字。如果两个数字的距离为零，则选择正数。

编辑回应埃里克的评论：

这里是一个具有相同的语义版本，但使用Min操作。它需要实施IComparable<>，所以我们可以使用Min，同时保留每个距离随附的数字。我也使它成为易用性的扩展方法：

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

我想这个数组是无序的。在订购它可以更快

我认为最简单和最快的方法是使用线性算法寻找最小值或最大值，而不是比较值，你会比较这个和针之间的差异的绝对值。

在C++（我不能C＃，但是这将是相似的）可以代码如下所示：

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

一般人在这个网站你会不会做你的功课。既然你没有发布代码，我也不会发布代码。但是，这是一种可能的方法。

遍历列表中，减去从x中的列表中的号码。取这个差值的绝对值，并将它与先前得到的最好结果进行比较，如果当前差值小于以前的最佳结果，则从列表中保存当前值。在循环结束时，你会得到你的答案。

Answer 6

懒惰我没有检查这一点，但不应该在该工作

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

哈斯克尔：

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