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

Question

我有一组常数数字，需要在这些数字中找到最接近x的数字。你们有什么实现该算法的想法吗？

- Alon Gubkin

---

别忘了考虑特殊情况。(1) 如果没有最接近的数怎么办？(2) 如果有两个不同的最接近的数怎么办？ - Eric Lippert

Answer 1

好的，你不能比 O(N) 更快地完成这个任务，因为你必须检查所有数字以确保你找到了最接近的一个。话虽如此，为什么不使用一种简单的变体来寻找最小值，即寻找与 x 的绝对差最小的那个数呢？

如果你能够确认列表从一开始就是有序的（并且它允许随机访问，比如数组），那么更好的方法是使用二分查找。当你在索引 i 处结束搜索（没有找到 x）时，只需从该元素及其相邻元素中选择最佳的一个。

- R. Martinho Fernandes

---

如果搜索的空间已经排序，你可以打败O(N)时间复杂度。 - Paolo

是的，使用二叉搜索树逻辑应该让你在O(log n)时间内完成。 - Kaleb Brasee

或者插值搜索，平均时间复杂度为O(log log n)。 - Malfist

也许我漏掉了什么，但您不能只是制作一个绝对数字abs（yourNum-needle）列表，将其放入数组中，然后进行排序吗？第一个索引应该是最接近的吧？ - mardala

@mardala 这是 O(N log N)，因为需要排序。 - R. Martinho Fernandes

Answer 2

我认为数组是无序的。如果有序，它会更快。

我认为最简单和最快的方法是使用线性算法查找最小或最大值，但是与其比较值，您将比较此和 needle 之间差的绝对值。

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

- Gaim

---

“needle”是我不知道的一些特殊术语吗？ - R. Martinho Fernandes

"大海捞针" - Johannes Rudolph

“needle”和“haystack”是经常与搜索算法一起使用的表达式。 - Gaim

尽管我们经常在不指望找到针的情况下使用“大海捞针”的表达方式！ - Phil Cooper

Answer 3

一般情况下，本站的用户不会替你完成作业。由于你没有贴出代码，我也不会提供代码。但是，以下是一种可能的方法：

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

- Bob Jarvis - Слава Україні

---

楼主确实使用了“作业”标签，他并没有试图欺骗您。 - Bryan Watts

Answer 4

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

根据Eric的评论进行编辑：

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

- Bryan Watts

---

好的，我按照“数字降序”排序，以确保选择正数（在没有行为要求的情况下，这是最合理的决定）。我会着手处理“Min”解决方案。感谢您的反馈，Eric！ - Bryan Watts

好的。小错误：numbers.Select(number => new NumberDistance(x, number) 应该是 numbers.Select(number => new NumberDistance(targetNumber, number)，对吗？ - John Kaster

@JohnKaster：你说得对。如果你不介意的话，我会进行编辑。 - Bryan Watts

@BryanWatts 刚刚完成了，谢谢。我想确认一下我没有踩到您的脚趾头。 :) - John Kaster

@JohnKaster：看到你的编辑被拒绝了 - 我自己进行了修改。感谢你的建议。 - Bryan Watts

Answer 5

因为太懒了我没有检查过，但这应该可以工作

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

- Peter J Fraser

Answer 6

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

- Thomas Eding

Answer 7

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

- Amit Srivastava

Answer 8

可以使用SortedList来完成：
关于查找最接近数字的博客文章
如果你只考虑搜索的复杂度，那么它是O(log(n))。列表构建将花费O(n*log(n))

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

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

意思是，从某个q开始，排序后的列表将提供更好的复杂度。

- Elisha