小编典典

使用键值范围的字典对象

c#

我需要一种专门的字典。我的用例是这样的:用户想要指定值的范围(范围也可以是单点),然后将值分配给特定范围。然后,我们想使用单个值作为键执行查找。如果此单个值出现在范围之一内,则我们将返回与该范围关联的值。

例如:

// represents the keyed value
struct Interval
{
    public int Min;
    public int Max;
}

// some code elsewhere in the program
var dictionary = new Dictionary<Interval, double>();
dictionary.Add(new Interval { Min = 0, Max = 10 }, 9.0);
var result = dictionary[1];
if (result == 9.0) JumpForJoy();

显然,这只是一些代码来说明我在寻找什么。有人知道实现这种事情的算法吗?如果可以的话,他们能指出我的方向吗?

我已经尝试实现自定义IEqualityComparer对象,并在Interval上重载Equals()和GetHashCode(),但到目前为止无济于事。可能是我做错了。


阅读 434

收藏
2020-05-19

共1个答案

小编典典

字典不是您要描述的操作的适当数据结构。

如果要求间隔永远不重叠,那么您可以构建间隔的排序列表并对其进行二进制搜索。

如果间隔可以重叠,那么您将面临一个更加困难的问题。为了有效地解决该问题,您需要构建一个间隔树:

http://en.wikipedia.org/wiki/Interval_tree

这是一个众所周知的数据结构。请参阅“算法简介”或有关数据结构的任何其他体面的本科生文章。

2020-05-19