如何在字典中找到离指定数字最近的键？

Question

我有一个Excel函数，现在想将其转化为对应的C#代码。该函数（在Excel中）如下：

WorksheetFunction.VLookup(number, Range("numberDictionary"), 2, True)

基本上这个函数的作用是...假设存在一个字典，定义如下:

Number | Value
1      | 2
3      | 8
9      | 1

假设我的参数“number”等于2。我期望返回一个值为8，因为查找函数会将我的输入数字2四舍五入到范围内最接近的数字（3），然后返回相关联的值。

请问有人能告诉我如何在C#代码中实现相同的功能吗？假设使用Dictionary()。

非常感谢！

Ian

- Ian

---

@HimBromBeere 在这种情况下，该函数将向上舍入到最近的键。 - Ian

你可以使用一个有序集合和二分查找算法。如果你坚持要用字典，那么时间复杂度将是 O(n)，因为你必须查看所有的键。 - Tim Schmelter

如果“number”是10（基本上是高于最高键的数字），会发生什么？ - juharr

Answer 1

你可以利用 IDictionary<TKey, TValue> 的 Keys 属性：

var dictionary = new Dictionary<int, int> { { 1, 2 }, { 3, 8 }, { 9, 1 } };
var key = dictionary.Keys.Where(a => a >= 2).OrderBy(a => a).First();
var value = dictionary[key];

- Albireo

Answer 2

如果您坚持使用字典，则可以使用以下LINQ查询：

Dictionary<int, int> dictionary = new Dictionary<int, int>() { 
    {1,2} ,{3,8} ,{9,1} 
};

int searchKey = 2;
int value;

if (dictionary.ContainsKey(searchKey))
    value = dictionary[searchKey];
else
{
    int nearestKey = dictionary.Keys
        .Select(i => new { Value = i, Diff = Math.Abs(i - searchKey) })
        .OrderBy(x => x.Diff)
        .ThenBy(x => x.Value > searchKey ? 0 : 1) // in case of ties you want the higher number
        .Select(x => x.Value)
        .First();
    value = dictionary[nearestKey];
}

这个时间复杂度为 O(n)，因为你需要查看所有的键。如果你可以使用有序集合和二分查找算法，那么它将是 O(log n)。所以你可以使用 SortedDictionary<TKey, TValue> 或者 SortedList<TKey, TValue>。它们之间的区别

使用 SortedList，你可以使用 这个扩展方法。然后就很简单了：

int index = dictionary.FindFirstIndexGreaterThanOrEqualTo(2);
int value = dictionary[dictionary.Keys[index]];

- Tim Schmelter

---

你的方法是O(N*log(N))，因为你要对整个集合进行排序才能搜索一个值。 - Servy

@Servy：你指的是哪个方法？我的第二种方法假设OP一开始使用了SortedList。我也不知道性能是否是OP的关键标准。 - Tim Schmelter

我指的是最初的版本，您建议对字典的整个内容进行排序，只为了找到一个值。 - Servy

@Servy：你在我编辑答案5分钟后才发表了评论。请随意提供更有效的方法。我相信一定有更好的方法。 - Tim Schmelter

Answer 3

        var input = 2;
        var dictionary = new Dictionary<int, int> { { 1, 2 }, { 3, 8 }, { 9, 1 } };

        var smallestDifference = int.MaxValue;
        var keys = new List<int>();

        if (dictionary.ContainsKey(input))
        {
            return dictionary[input];
        }

        foreach (var entry in dictionary)
        {
            var difference = entry.Key - input;
            if (difference < smallestDifference)
            {
                smallestDifference = difference;
                keys = new List<int>() { entry.Key };
            }
            else if (difference == smallestDifference)
            {
                keys.Add(entry.Key);
            }
        }

        var candidates = dictionary.Where(x => x.Key == smallestDifference).ToList();
        if ( candidates.Count == 1)
        {
            return candidates.SingleOrDefault();
        }
        return candidates.SingleOrDefault(y => y > input);

- Timon