在矩阵的任何子矩阵中找到最大元素 [英] Find the Maximum Element in any SubMatrix of Matrix

问题描述

我给出的矩阵为 N x M 。对于长度为 X 的子矩阵，其起始位置为（a，b），我必须在其中找到最大的元素一个子矩阵。

I am giving a Matrix of N x M. For a Submatrix of Length X which starts at position (a, b) i have to find the largest element present in a Submatrix.

我的方法：

1. 按照问题所述做：
   简单的2个循环

   for(i in range(a, a + x))
   for(j in range(b, b + x)) max = max(max,A[i][j]) // N * M

有点进步：

 1. Make a segment tree for every i in range(0, N)
 2. for i in range(a, a + x) query(b, b + x)    // N * logM

有没有更好的解决方案仅O（log n）复杂度？

Is there any better solution having O(log n) complexity only ?

推荐答案

一种稀疏表算法方法
：- < O（N×M×log（N）×log（M）），O（1）＞ 。


预计算时间- O（N x M x log（N）x log（M）） < br>
查询时间- O（1）


要了解此方法，您应该了解使用一维稀疏表算法查找RMQ的知识。

A Sparse Table Algorithm Approach :- <O( N x M x log(N) x log(M)) , O(1)>.

Precomputation Time - O( N x M x log(N) x log(M))
Query Time - O(1)

For understanding this method you should have knowledge of finding RMQ using sparse Table Algorithm for one dimension.

我们可以使用2D稀疏表算法查找范围最小查询。

We can use 2D Sparse Table Algorithm for finding Range Minimum Query.

我们在一维中的操作：-

我们对长度 RMQ > 2 ^ k 使用动态编程。我们将保留一个数组 M [0，N-1] [0，logN] 其中 M [i] [j] 是从 i 开始的子数组中最小值的索引。
为了计算 M [i] [j] ，我们必须在间隔的前一半和后一半中搜索最小值。很明显，小块的长度为 2 ^（j – 1），因此用于计算的伪代码为：-

What we do in One Dimension:-
we preprocess RMQ for sub arrays of length 2^k using dynamic programming. We will keep an array M[0, N-1][0, logN] where M[i][j] is the index of the minimum value in the sub array starting at i. For calculating M[i][j] we must search for the minimum value in the first and second half of the interval. It’s obvious that the small pieces have 2^(j – 1) length, so the pseudo code for calculation this is:-

if (A[M[i][j-1]] < A[M[i + 2^(j-1) -1][j-1]])
    M[i][j] = M[i][j-1]
else 
    M[i][j] = M[i + 2^(j-1) -1][j-1]

此处 A 是存储值的实际数组。一旦我们对这些值进行了预处理，就说明如何使用它们来计算 RMQ（i，j）。想法是选择两个完全覆盖区间 [i..j] 的块，并找出它们之间的最小值。设 k = [log（j-i + 1）] 。为了计算 RMQ（i，j），我们可以使用以下公式：-

Here A is actual array which stores values.Once we have these values preprocessed, let’s show how we can use them to calculate RMQ(i, j). The idea is to select two blocks that entirely cover the interval [i..j] and find the minimum between them. Let k = [log(j - i + 1)]. For computing RMQ(i, j) we can use the following formula:-

if (A[M[i][k]] <= A[M[j - 2^k + 1][k]])
    RMQ(i, j) = A[M[i][k]]
else 
    RMQ(i , j) = A[M[j - 2^k + 1][k]]

对于2维：-

同样，我们也可以将规则扩展到2维，这里我们使用动态编程&预处理长度 2 ^ K，2 ^ L 的子矩阵 RMQ 保持数组 M [0，N-1] [0，M-1] [0，logN] [0，logM] 。其中 M [x] [y] [k] [l] 是子矩阵中从 [x，y开始的最小值的索引] ，长度分别为 2 ^ K，2 ^ L 。用于计算 M [x] [y] [k] [l] 的
伪代码为：-

For 2 Dimension :-
Similarly We can extend above rule for 2 Dimension also , here we preprocess RMQ for sub matrix of length 2^K, 2^L using dynamic programming & keep an array M[0,N-1][0, M-1][0, logN][0, logM]. Where M[x][y][k][l] is the index of the minimum value in the sub matrix starting at [x , y] and having length 2^K, 2^L respectively. pseudo code for calculation M[x][y][k][l] is:-

M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1])

此处 GetMinimum 函数将从提供的元素中返回最小元素的索引。现在我们已经进行了预处理，让我们看看如何计算 RMQ（x，y，x1，y1）。这里 [x，y] 子矩阵的起点，而 [x1，y1] 代表子矩阵均值的终点子矩阵的右下角。在这里，我们必须选择四个完全覆盖 [x，y，x1，y1] 的子矩阵块，并找出其中的最小值。设 k = [log（x1-x + 1）] & l = [log（y1-y + 1）] 。为了计算 RMQ（x，y，x1，y1），我们可以使用以下公式：-

Here GetMinimum function will return the index of minimum element from provided elements. Now we have preprocessed, let's see how to calculate RMQ(x, y, x1, y1). Here [x, y] starting point of sub matrix and [x1, y1] represent end point of sub matrix means bottom right point of sub matrix. Here we have to select four sub matrices blocks that entirely cover [x, y, x1, y1] and find minimum of them. Let k = [log(x1 - x + 1)] & l = [log(y1 - y + 1)]. For computing RMQ(x, y, x1, y1) we can use following formula:-

RMQ(x, y, x1, y1) = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);

上述逻辑的伪代码：-

// remember Array 'M' store index of actual matrix 'P' so for comparing values in GetMinimum function compare the values of array 'P' not of array 'M' 
SparseMatrix(n , m){ // n , m is dimension of matrix.
    for i = 0 to 2^i <= n:
        for j = 0 to 2^j <= m:
            for x = 0 to x + 2^i -1 < n :
                for y = 0 to y + (2^j) -1 < m:
                    if i == 0 and j == 0:
                        M[x][y][i][j] = Pair(x , y) // store x, y
                    else if i == 0:
                        M[x][y][i][j] = GetMinimum(M[x][y][i][j-1], M[x][y+(2^(j-1))][i][j-1])
                    else if j == 0:
                        M[x][y][i][j] = GetMinimum(M[x][y][i-1][j], M[x+ (2^(i-1))][y][i-1][j])
                    else 
                        M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1]);
}
RMQ(x, y, x1, y1){
    k = log(x1 - x + 1)
    l = log(y1 - y + 1)
    ans = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);
    return P[ans->x][ans->y] // ans->x represent Row number stored in ans and similarly ans->y represent column stored in ans
}

这篇关于在矩阵的任何子矩阵中找到最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！