2

I have the following table:

block | start | end

1 | 1 | 4

2 | 5 | 9

3 | 10 | 20

4 | 21 | 50

..........

n | 1000 | 2000

When given a value to variable c i have to search which block contains c ( start < c < end ). For example when c = 1001, c is in block n. What data structure would be the most efficient?

4

5 回答 5

1

如果您的整数的整个范围是唯一的1..2000，您可以将您的数据视为如下表格：

n   block
1   1
2   1
3   1
4   0
5   0
6   2
.
.
.

您可以将其实现为 2000 个元素的向量。简单查找n向量中的元素将告诉您哪个块n在其中（除非您选择使用基于 0 的索引的语言来实现，在这种情况下元素n会告诉您哪个块整数n+1在）。在这里，我使用 0 表示“无阻塞”。

与这里的其他一些答案相比，这以空间换时间，但这通常是可以接受的权衡。

于 2012-07-05T15:31:14.680 回答
1

区间树或段树会起作用。本质上，您可以通过区间进行二分搜索以找到包含问题点的区间。由于 Segment Tree 更擅长刺探查询，因此我会首先尝试。

如果您使用的是 Java，我之前已经在 java 中实现了它们。您可以在此处找到区间树和在此处找到段树。

于 2012-07-05T15:46:59.047 回答
1

我认为，区间树非常适合这个问题。它肯定比表格更难实现，如果您不需要动态添加块，我建议只保留表格并使用简单的二进制搜索来查找块。这应该达到与间隔树相同的效率，而没有所有可怕的编码痛苦（只要您不必添加间隔）。

于 2012-07-05T15:47:59.063 回答
0

我不确定你在问什么

我相信有很多方法可以实现这样的块，我个人会有一个包含每个块结尾的排序列表并运行它直到结尾大于值，索引给我块的数量

于 2012-07-05T14:59:08.110 回答
0

对于这个特定的示例，您可以将 start 存储在一个数组中（按排序顺序）并进行二进制搜索以到达适当的块。

编辑解释示例：

在起始数组中，您有 1,5,10,21,1000，因此对于 c=3，您知道它在块 1 中，因为 5 是块 2 的起始索引。

出于某种原因，如果您还想查看 end 那么您可以将其存储在另一个数组中，并从您从二进制搜索中获得的索引访问 start 的结尾。

于 2012-07-05T15:00:19.623 回答