C# 在数字列表中找到最接近的数字

Find the closest number in a list of numbers

提问by Alon Gubkin

I have a list of constant numbers. I need to find the closest number to x in the list of the numbers. Any ideas on how to implement this algorithm?

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

采纳答案by R. Martinho Fernandes

Well, you cannot do this faster than O(N)because you have to check all numbers to be sure you have the closest one. That said, why not use a simple variation on finding the minimum, looking for the one with the minimum absolute difference with x?

好吧，您不能比这更快地做到这一点，O(N)因为您必须检查所有数字以确保您拥有最接近的数字。也就是说，为什么不使用一个简单的变体来寻找最小值，寻找与x具有最小绝对差异的那个？

If you can say the list is ordered from the beginning (and it allows random-access, like an array), then a better approach is to use a binary search. When you end the search at index i(without finding x), just pick the best out of that element and its neighbors.

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

回答by Elisha

It can be done using SortedList:
Blog post on finding closest number
If the complexity you're looking for counts only the searching the complexity is O(log(n)). The list building will cost O(n*log(n))

可以使用SortedList来完成：
关于寻找最接近数字的博客文章
如果您正在寻找的复杂度仅计算搜索的复杂度为O(log(n))。列表构建将花费O(n*log(n))

If you're going to insert item to the list much more times than you're going to query it for the closest number then the best choice is to use Listand use naive algorithm to query it for the closest number. Each search will cost O(n)but time to insert will be reduced to O(n).

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

General complexity: If the collection has nnumbers and searched qtimes -
List: O(n+q*n)
Sorted List: O(n*log(n)+q*log(n))

一般复杂度：如果集合有n 个数字并搜索了q次 -
List: O(n+q*n)
Sorted List：O(n*log(n)+q*log(n))

Meaning, from some qthe sorted list will provide better complexity.

意思是，从某些q排序列表将提供更好的复杂性。

回答by Bryan Watts

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 means there was no closest number. If there are two numbers with the same difference, it will choose the one closest to zero. If two numbers are the same distance from zero, the positive number will be chosen.

Null 表示没有最接近的数字。如果有两个相差相同的数字，它会选择最接近零的一个。如果两个数字到零的距离相同，则将选择正数。

Edit in response to Eric's comment:

编辑回应埃里克的评论：

Here is a version which has the same semantics, but uses the Minoperator. It requires an implementation of IComparable<>so we can use Minwhile preserving the number that goes with each distance. I also made it an extension method for ease-of-use:

这是一个具有相同语义但使用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;
    }
}

回答by Gaim

I suppose that the array is unordered. In ordered it can be faster

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

I think that the simpliest and the fastest method is using linear algorithm for finding minimum or maximum but instead of comparing values you will compare absolute value of difference between this and needle.

我认为最简单和最快的方法是使用线性算法来查找最小值或最大值，但不是比较值，而是比较 this 和 pin 之间差异的绝对值。

In the C++ ( I can't C# but it will be similar ) can code look like this:

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

回答by Bob Jarvis - Reinstate Monica

In general people on this site won't do your homework for you. Since you didn't post code I won't post code either. However, here's one possible approach.

一般来说，这个网站上的人不会为你做功课。由于您没有发布代码，我也不会发布代码。但是，这是一种可能的方法。

Loop through the list, subtracting the number in the list from x. Take the absolute value of this difference and compare it to the best previous result you've gotten and, if the current difference is less than the best previous result, save the current number from the list. At the end of the loop you'll have your answer.

循环遍历列表，从 x 中减去列表中的数字。取该差值的绝对值并将其与您获得的最佳先前结果进行比较，如果当前差值小于先前最佳结果，则从列表中保存当前数字。在循环结束时，您将得到答案。

回答by Peter J Fraser

Being lazy I have not check this but shouldn't this work

懒惰我没有检查这个但不应该这个工作

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

回答by Thomas Eding

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

回答by Amit Srivastava

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