Trova l'elemento massimo in qualsiasi sottomaschermo di matrice

Question

Fornisco una matrice di N x M. Per una Submatrix di lunghezza X che inizia alla posizione (a, b) devo trovare l'elemento più grande presente in una Submatrix.

mio approccio:

1. Do la questione dice: semplici 2 loop

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

Un po 'Advance:

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 

Esiste una soluzione migliore che abbia solo complessità O (log n)?

Answer 1

AFAIK, non ci può essere O (approccio logn) poiché la matrice non segue alcun ordine. Tuttavia, se hai un ordine in modo che ogni riga sia ordinata in ordine ascendente da sinistra a destra e ogni colonna sia ordinata in ordine crescente da alto a basso, allora sai che A [a + x] [b + x] (cella in basso a destra della sottomatrice) è l'elemento più grande in quella sottomatrice. Quindi, trovare il massimo richiede O (1) tempo dopo aver ordinato la matrice. Tuttavia, l'ordinamento della matrice, se non già ordinato, avrà un costo O (NxM log {NxM})

Answer 2

A Approccio algoritmo tabella sparse : - <O(N x M x log(N) x log(M)) , O(1)>.

precomputation Tempo-O(N x M x log(N) x log(M))
Tempo Query-O(1)

Per capire questo metodo si dovrebbe avere la conoscenza di trovare RMQ utilizzando l'algoritmo tabella sparsa per una dimensione.

È possibile utilizzare l'algoritmo di tabelle sparse 2D per trovare la query minima di intervallo.

Quello che facciamo in una dimensione: -
abbiamo preprocess RMQ per sub array di lunghezza 2^k usando la programmazione dinamica. Manterremo un array M[0, N-1][0, logN] doveè l'indice del valore minimo nel sottararray a partire da i. Per il calcolo di M[i][j] dobbiamo cercare il valore minimo nella prima e nella seconda parte dell'intervallo. E 'ovvio che i piccoli pezzi hanno 2^(j – 1) lunghezza, in modo che il codice di pseudo per il calcolo questo è: -

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] 

Qui A è gamma attuale che memorizza values.Once abbiamo questi valori pre-elaborato, cerchiamo di mostrare come possiamo li usa per calcolare RMQ (i, j). L'idea è di selezionare due blocchi che coprano interamente l'intervallo [i..j] e trovare il minimo tra di loro. Lasciare k = [log(j - i + 1)].Per il calcolo RMQ (i, j) possiamo usare la seguente 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]] 

Per 2 Dimensione: -
Allo stesso modo possiamo estendere sopra regola per 2 Dimension anche, qui ci preprocess RMQ per sottomatrice di lunghezza 2^K, 2^L utilizzando la programmazione dinamica & mantenere un array M[0,N-1][0, M-1][0, logN][0, logM]. Dove M[x][y][k][l] è l'indice del valore minimo nella sottomaschera a partire da [x , y] e con lunghezza 2^K, 2^L rispettivamente. pseudo codice per il calcolo M[x][y][k][l] è: -

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]) 

Qui funzione GetMinimum restituisce l'indice dell'elemento minimo da elementi previsti. Ora abbiamo preelaborato, vediamo come calcolare RMQ (x, y, x1, y1). Qui il punto iniziale della sottomaschera [x, y] e [x1, y1] rappresentano il punto finale della sottomaschera che indica il punto in basso a destra della sottomatrice. Qui dobbiamo selezionare quattro blocchi di sottostrutture che coprono interamente [x, y, x1, y1] e trovano il minimo di essi. Let k = [log(x1 - x + 1)] & l = [log(y1 - y + 1)]. Per calcolare RMQ (x, y, x1, y1) possiamo utilizzare seguente 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]); 

pseudo codice per la logica di cui sopra: -

// 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 
} 

Answer 3

Ecco campione codice in C++, per lo pseudo codice dato da @Chapta, come richiesto da qualche utente.

int M[1000][1000][10][10]; 
int **matrix; 

void precompute_max(){ 
    for (int i = 0 ; (1<<i) <= n; i += 1){ 
     for(int j = 0 ; (1<<j) <= m ; j += 1){ 
      for (int x = 0 ; x + (1<<i) -1 < n; x+= 1){ 
       for (int y = 0 ; y + (1<<j) -1 < m; y+= 1){ 
        if (i == 0 and j == 0) 
         M[x][y][i][j] = matrix[x][y]; // store x, y 
        else if (i == 0) 
         M[x][y][i][j] = max(M[x][y][i][j-1], M[x][y+(1<<(j-1))][i][j-1]); 
        else if (j == 0) 
         M[x][y][i][j] = max(M[x][y][i-1][j], M[x+ (1<<(i-1))][y][i-1][j]); 
        else 
         M[x][y][i][j] = max(M[x][y][i-1][j-1], M[x + (1<<(i-1))][y][i-1][j-1], M[x][y+(1<<(j-1))][i-1][j-1], M[x + (1<<(i-1))][y+(1<<(j-1))][i-1][j-1]); 
        // cout << "from i="<<x<<" j="<<y<<" of length="<<(1<<i)<<" and length="<<(1<<j) <<"max is: " << M[x][y][i][j] << endl; 
       } 
      } 
     } 
    } 
} 

int compute_max(int x, int y, int x1, int y1){ 
    int k = log2(x1 - x + 1); 
    int l = log2(y1 - y + 1); 
    // cout << "Value of k="<<k<<" l="<<l<<endl; 
    int ans = max(M[x][y][k][l], M[x1 - (1<<k) + 1][y][k][l], M[x][y1 - (1<<l) + 1][k][l], M[x1 - (1<<k) + 1][y1 - (1<<l) + 1][k][l]); 
    return ans; 
} 

Questo codice primi precomputes, la tabella sparsa dimensionale 2, e quindi interroga in tempo costante. Ulteriori informazioni: la tabella sparse memorizza l'elemento massimo e non gli indici sull'elemento massimo.