1

对于具有整数值的 NxM 矩阵，找到区域 (x1,y1) (x2,y2) 的最小元素的最有效方法是什么，其中 0 <= x1<=x2 < M 和 0 <= y1 <= y2 < N

我们可以假设我们将多次查询不同的区域。

我想知道我们是否可以将范围最小查询方法扩展到这个问题。 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

非常简单的解决方案可以是使用 RMQ（段树）最有效的解决方案，然后逐行或逐列地应用它。

最坏情况的复杂度是 min(N,M)*log(max(N,M))

但我仍然相信我们可以做得更好。

4

3 回答 3

2

鉴于没有关于矩阵内容或存储方式的其他信息，除了扫描给定区域中的每个条目之外，不可能提出任何建议。那是O((x2-x1) * (y2-y1))。你的问题太模糊了，不能说别的。

如果您对矩阵有所了解，例如，如果您知道元素可能以某种方式排序，您可能会做得更好（概率上，在平均情况下）。

于 2013-01-09T21:09:16.637 回答
2

这取决于您所说的“最有效的方式”是什么意思。可以最大限度地减少查询时间本身、预处理时间或内存需求。

如果只应该最小化查询时间，“最有效的方法”是预先计算所有可能的区域。然后通过返回一些预先计算的值来处理每个查询。查询时间为 O(1)。内存和预处理时间都很大：O((NM) 2 )。

更实用的是使用OP 中提到的页面中的稀疏表算法。该算法准备了一个包含所有二次幂长度区间的表，并使用一对这些区间来处理任何范围最小查询。查询时间为 O(1)。内存和预处理时间为 O(N log N)。并且该算法可以很容易地扩展到二维情况。

2D 中的稀疏表算法

只需准备一个包含所有长度为 2 的幂和高度为 2 的幂的矩形的表，并使用其中四个矩形来处理任何范围最小查询。结果是每个矩形至少有四个最小值。查询时间为 O(1)。内存和预处理时间为 O(NM*log(N)*log(M))。

这篇论文：Amihood Amir、Johannes Fischer 和 Moshe Lewenstein 的“二维范围最小查询”提出了如何将该算法的内存需求和预处理时间减少到几乎 O(MN)。

这篇论文：Hao Yuan 和 Mikhail J. Atallah 的“Data Structures for Range Minimum Queries in Multidimensional Arrays”给出了具有 O(1) 查询时间和 O(NM) 内存和预处理时间的不同算法。

于 2013-01-10T14:59:02.413 回答
0

伪代码：

function getMax(M, x1, x2, y1, y2)
    max = M[x1,y1]
    for x = x1 to x2 do
        for y = y1 to y2 do
            if M[x,y] > max then max = M[x, y]
    return max

这是输入大小中的 O(n)，只能合理地解释为矩阵区域 (x2 - x1) * (y2 - y1) 的大小。如果您想要最小值，请将 max 更改为 min 并将 > 更改为 <。您不能做得比 O(n) 更好，即检查每个可能的元素。假设你有一个比 O(n) 更快的算法。然后它不会检查所有元素。要获得算法的失败案例，请取出它不检查的元素之一，并将其​​替换为 (max + 1)，然后重新运行算法。

于 2013-01-09T21:08:59.350 回答