Dada una array binaria mat[][] de tamaño M * N y Q consultas de la forma {pi, pj, qi, qj} , la tarea para cada consulta es contar el número de 0 s en la subarray de la celda ( pi, pj) a (qi, qj) .
Ejemplos:
Entrada: mat[][] = {{0, 1, 0, 1, 1, 1, 0}, {1, 0, 1, 1, 1, 0, 1}, {1, 1, 0, 0, 1, 1, 0}, {1, 1, 1, 1, 1, 0, 1}, {0, 0, 1, 0, 1, 1, 1}, {1, 1, 0, 1, 1, 0, 1 }}, Q[] = {{0, 1, 3, 2}, {2, 2, 4, 5}, {4, 3, 5, 6}}
Salida: 3 4 2
Explicación:
La subarray de los índices (0, 1) a (3, 2) contiene 3 0s.
La subarray de los índices (2, 2) a (4, 5) contiene 4 0s.
La subarray de los índices (4, 3) a (5, 6) contiene 2 0s.Entrada: mat[][] = {{0, 1, 0}, {1, 0, 1}}, Q[] = {{0, 0, 2, 2}}
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema es contar el número de 0 para cada consulta iterando la subarray e imprimir el recuento para cada consulta.
Complejidad temporal: O(M*N*Q)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es preprocesar la array dada mat[][] . Cree una array de conteo, digamos prefixCnt[M][N] , tal que prefix_cnt[i][j] almacene el conteo de 0 s en la subarray dentro de los índices (0, 0) a (i, j) . Siga los pasos a continuación para calcular prefixCnt[][] :
- Inicialice prefixCnt[i][j] con 1 si mat[i][j] es 0 . De lo contrario, inicialice con 0 .
- Encuentre la suma del prefijo para cada fila y columna y actualice la array en consecuencia.
Una vez que se calcula el prefijo de array Cnt [] [] , el recuento de 0 en cualquier subarray se puede evaluar en tiempo O (1) . A continuación se muestra la expresión para contar los 0 en cada subarray desde (pi, pj) hasta (qi, qj) se puede calcular mediante:
cnt = prefijoCnt[qi][qj] – prefijoCnt[pi-1][qj] – prefijoCnt[qi][pj – 1] + prefijoCnt[pi – 1][pj – 1]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define M 6 #define N 7 // Function to compute the matrix // prefixCnt[M][N] from mat[M][N] such // that prefixCnt[i][j] stores the // count of 0's from (0, 0) to (i, j) void preCompute(int mat[M][N], int prefixCnt[M][N]) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // Initialize prefixCnt[i][j] // with 1 if mat[i][j] is 0 if (mat[i][j] == 0) { prefixCnt[i][j] = 1; } // Otherwise, assign with 0 else { prefixCnt[i][j] = 0; } } } // Calculate prefix sum for each row for (int i = 0; i < M; i++) for (int j = 1; j < N; j++) prefixCnt[i][j] += prefixCnt[i][j - 1]; // Calculate prefix sum for each column for (int i = 1; i < M; i++) for (int j = 0; j < N; j++) prefixCnt[i][j] += prefixCnt[i - 1][j]; } // Function to compute count of 0's // in submatrix from (pi, pj) to // (qi, qj) from prefixCnt[M][N] int countQuery(int prefixCnt[M][N], int pi, int pj, int qi, int qj) { // Initialize that count of 0's // in the sub-matrix within // indices (0, 0) to (qi, qj) int cnt = prefixCnt[qi][qj]; // Subtract count of 0's within // indices (0, 0) and (pi-1, qj) if (pi > 0) cnt -= prefixCnt[pi - 1][qj]; // Subtract count of 0's within // indices (0, 0) and (qi, pj-1) if (pj > 0) cnt -= prefixCnt[qi][pj - 1]; // Add prefixCnt[pi - 1][pj - 1] // because its value has been added // once but subtracted twice if (pi > 0 && pj > 0) cnt += prefixCnt[pi - 1][pj - 1]; return cnt; } // Function to count the 0s in the // each given submatrix void count0s(int mat[M][N], int Q[][4], int sizeQ) { // Stores the prefix sum of each // row and column int prefixCnt[M][N]; // Compute matrix prefixCnt[][] preCompute(mat, prefixCnt); for (int i = 0; i < sizeQ; i++) { // Function Call for each query cout << countQuery(prefixCnt, Q[i][0], Q[i][1], Q[i][2], Q[i][3]) << ' '; } } // Driver Code int main() { // Given matrix int mat[M][N] = { { 0, 1, 0, 1, 1, 1, 0 }, { 1, 0, 1, 1, 1, 0, 1 }, { 1, 1, 0, 0, 1, 1, 0 }, { 1, 1, 1, 1, 1, 0, 1 }, { 0, 0, 1, 0, 1, 1, 1 }, { 1, 1, 0, 1, 1, 0, 1 } }; int Q[][4] = { { 0, 1, 3, 2 }, { 2, 2, 4, 5 }, { 4, 3, 5, 6 } }; int sizeQ = sizeof(Q) / sizeof(Q[0]); // Function Call count0s(mat, Q, sizeQ); return 0; }
Java
// Java program for the above approach class GFG{ final static int M = 6; final static int N = 7; // Function to compute the matrix // prefixCnt[M][N] from mat[M][N] such // that prefixCnt[i][j] stores the // count of 0's from (0, 0) to (i, j) static void preCompute(int mat[][], int prefixCnt[][]) { for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { // Initialize prefixCnt[i][j] // with 1 if mat[i][j] is 0 if (mat[i][j] == 0) { prefixCnt[i][j] = 1; } // Otherwise, assign with 0 else { prefixCnt[i][j] = 0; } } } // Calculate prefix sum for each row for(int i = 0; i < M; i++) for(int j = 1; j < N; j++) prefixCnt[i][j] += prefixCnt[i][j - 1]; // Calculate prefix sum for each column for(int i = 1; i < M; i++) for(int j = 0; j < N; j++) prefixCnt[i][j] += prefixCnt[i - 1][j]; } // Function to compute count of 0's // in submatrix from (pi, pj) to // (qi, qj) from prefixCnt[M][N] static int countQuery(int prefixCnt[][], int pi, int pj, int qi, int qj) { // Initialize that count of 0's // in the sub-matrix within // indices (0, 0) to (qi, qj) int cnt = prefixCnt[qi][qj]; // Subtract count of 0's within // indices (0, 0) and (pi-1, qj) if (pi > 0) cnt -= prefixCnt[pi - 1][qj]; // Subtract count of 0's within // indices (0, 0) and (qi, pj-1) if (pj > 0) cnt -= prefixCnt[qi][pj - 1]; // Add prefixCnt[pi - 1][pj - 1] // because its value has been added; // once but subtracted twice if (pi > 0 && pj > 0) cnt += prefixCnt[pi - 1][pj - 1]; return cnt; } // Function to count the 0s in the // each given submatrix static void count0s(int mat[][], int Q[][], int sizeQ) { // Stores the prefix sum of each // row and column int prefixCnt[][] = new int[M][N]; // Compute matrix prefixCnt[][] preCompute(mat, prefixCnt); for(int i = 0; i < sizeQ; i++) { // Function Call for each query System.out.print(countQuery(prefixCnt, Q[i][0], Q[i][1], Q[i][2], Q[i][3]) + " "); } } // Driver Code public static void main (String[] args) { // Given matrix int mat[][] = { { 0, 1, 0, 1, 1, 1, 0 }, { 1, 0, 1, 1, 1, 0, 1 }, { 1, 1, 0, 0, 1, 1, 0 }, { 1, 1, 1, 1, 1, 0, 1 }, { 0, 0, 1, 0, 1, 1, 1 }, { 1, 1, 0, 1, 1, 0, 1 } }; int Q[][] = { { 0, 1, 3, 2 }, { 2, 2, 4, 5 }, { 4, 3, 5, 6 } }; int sizeQ = Q.length; // Function Call count0s(mat, Q, sizeQ); } } // This code is contributed by AnkThon
Python3
# Python3 program for the above approach M = 6 N = 7 # Function to compute the matrix # prefixCnt[M][N] from mat[M][N] such # that prefixCnt[i][j] stores the # count of 0's from (0, 0) to (i, j) def preCompute(mat, prefixCnt): for i in range(M): for j in range(N): # Initialize prefixCnt[i][j] # with 1 if mat[i][j] is 0 if (mat[i][j] == 0): prefixCnt[i][j] = 1 # Otherwise, assign with 0 else: prefixCnt[i][j] = 0 # Calculate prefix sum for each row for i in range(M): for j in range(1, N): prefixCnt[i][j] += prefixCnt[i][j - 1] # Calculate prefix sum for each column for i in range(1, M): for j in range(N): prefixCnt[i][j] += prefixCnt[i - 1][j] return prefixCnt # Function to compute count of 0's # in submatrix from (pi, pj) to # (qi, qj) from prefixCnt[M][N] def countQuery(prefixCnt, pi, pj, qi, qj): # Initialize that count of 0's # in the sub-matrix within # indices (0, 0) to (qi, qj) cnt = prefixCnt[qi][qj] # Subtract count of 0's within # indices (0, 0) and (pi-1, qj) if (pi > 0): cnt -= prefixCnt[pi - 1][qj] # Subtract count of 0's within # indices (0, 0) and (qi, pj-1) if (pj > 0): cnt -= prefixCnt[qi][pj - 1] # Add prefixCnt[pi - 1][pj - 1] # because its value has been added # once but subtracted twice if (pi > 0 and pj > 0): cnt += prefixCnt[pi - 1][pj - 1] return cnt # Function to count the 0s in the # each given submatrix def count0s(mat, Q, sizeQ): # Stores the prefix sum of each # row and column prefixCnt = [[ 0 for i in range(N)] for i in range(M)] # Compute matrix prefixCnt[][] prefixCnt = preCompute(mat, prefixCnt) for i in range(sizeQ): # Function Call for each query print(countQuery(prefixCnt, Q[i][0], Q[i][1], Q[i][2], Q[i][3]), end=" ") # Driver Code if __name__ == '__main__': # Given matrix mat = [[ 0, 1, 0, 1, 1, 1, 0 ], [ 1, 0, 1, 1, 1, 0, 1 ], [ 1, 1, 0, 0, 1, 1, 0 ], [ 1, 1, 1, 1, 1, 0, 1 ], [ 0, 0, 1, 0, 1, 1, 1 ], [ 1, 1, 0, 1, 1, 0, 1 ] ] Q= [ [ 0, 1, 3, 2 ], [ 2, 2, 4, 5 ], [ 4, 3, 5, 6 ] ] sizeQ = len(Q) # Function Call count0s(mat, Q, sizeQ) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; class GFG { static int M = 6; static int N = 7; // Function to compute the matrix // prefixCnt[M][N] from mat[M][N] such // that prefixCnt[i][j] stores the // count of 0's from (0, 0) to (i, j) static void preCompute(int [,]mat, int [,]prefixCnt) { for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { // Initialize prefixCnt[i][j] // with 1 if mat[i,j] is 0 if (mat[i, j] == 0) { prefixCnt[i, j] = 1; } // Otherwise, assign with 0 else { prefixCnt[i, j] = 0; } } } // Calculate prefix sum for each row for(int i = 0; i < M; i++) for(int j = 1; j < N; j++) prefixCnt[i, j] += prefixCnt[i, j - 1]; // Calculate prefix sum for each column for(int i = 1; i < M; i++) for(int j = 0; j < N; j++) prefixCnt[i, j] += prefixCnt[i - 1, j]; } // Function to compute count of 0's // in submatrix from (pi, pj) to // (qi, qj) from prefixCnt[M][N] static int countQuery(int [,]prefixCnt, int pi, int pj, int qi, int qj) { // Initialize that count of 0's // in the sub-matrix within // indices (0, 0) to (qi, qj) int cnt = prefixCnt[qi, qj]; // Subtract count of 0's within // indices (0, 0) and (pi-1, qj) if (pi > 0) cnt -= prefixCnt[pi - 1, qj]; // Subtract count of 0's within // indices (0, 0) and (qi, pj-1) if (pj > 0) cnt -= prefixCnt[qi, pj - 1]; // Add prefixCnt[pi - 1][pj - 1] // because its value has been added; // once but subtracted twice if (pi > 0 && pj > 0) cnt += prefixCnt[pi - 1, pj - 1]; return cnt; } // Function to count the 0s in the // each given submatrix static void count0s(int [,]mat, int [,]Q, int sizeQ) { // Stores the prefix sum of each // row and column int [,]prefixCnt = new int[M, N]; // Compute matrix prefixCnt[,] preCompute(mat, prefixCnt); for(int i = 0; i < sizeQ; i++) { // Function Call for each query Console.Write(countQuery(prefixCnt, Q[i, 0], Q[i, 1], Q[i, 2], Q[i, 3]) + " "); } } // Driver Code public static void Main(string[] args) { // Given matrix int [,]mat = { { 0, 1, 0, 1, 1, 1, 0 }, { 1, 0, 1, 1, 1, 0, 1 }, { 1, 1, 0, 0, 1, 1, 0 }, { 1, 1, 1, 1, 1, 0, 1 }, { 0, 0, 1, 0, 1, 1, 1 }, { 1, 1, 0, 1, 1, 0, 1 } }; int [,]Q = { { 0, 1, 3, 2 }, { 2, 2, 4, 5 }, { 4, 3, 5, 6 } }; int sizeQ = Q.GetLength(0); // Function Call count0s(mat, Q, sizeQ); } } // This code is contributed by AnkThon
Javascript
<script> // javascript program of the above approach let M = 6; let N = 7; // Function to compute the matrix // prefixCnt[M][N] from mat[M][N] such // that prefixCnt[i][j] stores the // count of 0's from (0, 0) to (i, j) function preCompute(mat, prefixCnt) { for(let i = 0; i < M; i++) { for(let j = 0; j < N; j++) { // Initialize prefixCnt[i][j] // with 1 if mat[i][j] is 0 if (mat[i][j] == 0) { prefixCnt[i][j] = 1; } // Otherwise, assign with 0 else { prefixCnt[i][j] = 0; } } } // Calculate prefix sum for each row for(let i = 0; i < M; i++) for(let j = 1; j < N; j++) prefixCnt[i][j] += prefixCnt[i][j - 1]; // Calculate prefix sum for each column for(let i = 1; i < M; i++) for(let j = 0; j < N; j++) prefixCnt[i][j] += prefixCnt[i - 1][j]; } // Function to compute count of 0's // in submatrix from (pi, pj) to // (qi, qj) from prefixCnt[M][N] function countQuery(prefixCnt, pi, pj, qi, qj) { // Initialize that count of 0's // in the sub-matrix within // indices (0, 0) to (qi, qj) let cnt = prefixCnt[qi][qj]; // Subtract count of 0's within // indices (0, 0) and (pi-1, qj) if (pi > 0) cnt -= prefixCnt[pi - 1][qj]; // Subtract count of 0's within // indices (0, 0) and (qi, pj-1) if (pj > 0) cnt -= prefixCnt[qi][pj - 1]; // Add prefixCnt[pi - 1][pj - 1] // because its value has been added; // once but subtracted twice if (pi > 0 && pj > 0) cnt += prefixCnt[pi - 1][pj - 1]; return cnt; } // Function to count the 0s in the // each given submatrix function count0s(mat, Q, sizeQ) { // Stores the prefix sum of each // row and column let prefixCnt = new Array(M); // Loop to create 2D array using 1D array for (var i = 0; i < prefixCnt.length; i++) { prefixCnt[i] = new Array(2); } // Compute matrix prefixCnt[][] preCompute(mat, prefixCnt); for(let i = 0; i < sizeQ; i++) { // Function Call for each query document.write(countQuery(prefixCnt, Q[i][0], Q[i][1], Q[i][2], Q[i][3]) + " "); } } // Driver Code // Given matrix let mat = [[ 0, 1, 0, 1, 1, 1, 0 ], [ 1, 0, 1, 1, 1, 0, 1 ], [ 1, 1, 0, 0, 1, 1, 0 ], [ 1, 1, 1, 1, 1, 0, 1 ], [ 0, 0, 1, 0, 1, 1, 1 ], [ 1, 1, 0, 1, 1, 0, 1 ]]; let Q = [[ 0, 1, 3, 2 ], [ 2, 2, 4, 5 ], [ 4, 3, 5, 6 ]]; let sizeQ = Q.length; // Function Call count0s(mat, Q, sizeQ); // This code is contributed by target_2. </script>
3 4 2
Complejidad temporal: O(M*N + Q)
Espacio auxiliar: O(M*N)
Publicación traducida automáticamente
Artículo escrito por sunidhichandra27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA