Dada una array binaria de tamaño NxN que inicialmente se llena con 0 y consultas Q tales que:
- Cada consulta es de tipo (r, c) donde r y c denotan el número de fila y el número de columna respectivamente.
- Cambie todos los 0 de la fila r y la columna c a 1.
La tarea es encontrar el conteo de 0 después de realizar cada consulta en la array dada.
Ejemplos:
Entrada: N = 3, Q = 3, consultas = {{2, 2}, {2, 3}, {3, 2}}
Salida: 4 2 1
Explicación: Después de la 1.ª operación, toda la 2.ª fila y toda la 2.ª la columna se llenará con 1. Por lo tanto, la celda restante con valor 0 será 4.
Después de la 2.ª operación, toda la 2.ª fila y toda la 3.ª columna se rellenarán con 1. Por lo tanto, la celda restante con valor 0 será 2.
Después de la 3.ª operación, las celdas teniendo valor 0 será 1.Entrada: N = 4, Q = 3, consultas = {{3, 1}, {3, 3}, {4, 2}}
Salida: 9 6 3
Explicación: Después de la primera operación, toda la tercera fila y toda la primera la columna se llenará con 1. Por lo tanto, la celda restante con valor 0 será 9.
Después de la 2.ª operación, toda la 3.ª fila y toda la 3.ª columna se rellenarán con 1. Por lo tanto, la celda restante con valor 0 será 6.
Después de la 3.ª Las celdas de operación que tengan valor 0 serán 3.
Enfoque ingenuo: el enfoque básico para resolver este problema es actualizar los elementos de la array para los elementos de la fila y la columna mencionados para una consulta y luego recorrer toda la array para encontrar el recuento de ceros restantes. Este proceso se repetirá para todas las consultas Q.
Complejidad de Tiempo: O(Q*(N+N 2 )) = O(Q*(N 2 ))
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar eliminando la necesidad de atravesar la array para consultas Q con la ayuda de hashing .
- Cree una array hash para almacenar la fila y la columna escaneadas.
- Declare las variables r y c para almacenar el recuento de 0 presente en la fila y la columna y declare ans y almacene NxN .
- Ahora comience a recorrer la array dada , y en cada iteración:
- Compruebe si la fila y la columna actuales ya existen o no en la array hash.
- Si la fila actual no está presente, reste r de ans y disminuya el valor de c en 1.
- Si la columna actual no está presente, reste la c dada de ans y disminuya el valor de r en 1.
- Empuje y en vector.
Ilustración:
Considere la array:
N=3
0 0 0
0 0 0
0 0 0
Inicialmente ans=n*n=9, r=3(Número de ceros en la fila) y c=3(Número de ceros en la columna)
Recorrer cada consulta dada
por ejemplo, consultas = {{2, 2}, {2, 3}, {3, 2}}
Seleccione la primera fila de consulta = 2 y la columna = 2, verifique si esta fila o columna ya se convirtió en una o no usando hashmap.
Aquí fila=2 no se visita, así que convierta todos los ceros presentes en esa fila en uno, es decir, ans-=r, debido a que este número de ceros en cada columna se reduce en 1, es decir, c–.
0 0 0
1 1 1
0 0 0
Ahora ans=9-3=6, r=3(Número de ceros en la fila) y c=2(Número de ceros en la columna)
Aquí col=2 no se visita en la primera consulta, así que convierta todos los ceros presentes en esa columna en uno, es decir, ans-=c, debido a que este número de ceros en cada fila se reduce en 1, es decir, r–.
0 1 0
1 1 1
0 1 0
Ahora ans=6-2=4, r=2(Número de ceros en la fila) y c=2(Número de ceros en la columna)
Entonces, después de la ejecución de la primera consulta, el número de ceros restantes es 4.
Seleccione la segunda fila de consulta = 2 y la columna = 3, verifique si esta fila o columna ya se convirtió en una o no usando hashmap.
Aquí la fila = 2 ya se visitó, así que simplemente continúe.
Aquí col=3 no se visita en la primera consulta, así que convierta todos los ceros presentes en esa columna en uno, es decir, ans-=c, debido a que este número de ceros en cada fila se reduce en 1, es decir, r–.
0 1 1
1 1 1
0 1 1
Ahora ans=4-2=2, r=1(Número de ceros en la fila) y c=2(Número de ceros en la columna)
Entonces, después de la ejecución de la segunda consulta, el número de ceros restantes es 2.
Repita el proceso para todas las consultas.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach.
#include <bits/stdc++.h>
using namespace std;
vector<long long int> countZero(
int n, int k,
vector<vector<int> >& arr)
{
long long int ans = n, r = n, c = n;
// for declaring n*n matrix
ans *= ans;
vector<bool> row(n + 1, true), col(n + 1, true);
vector<long long int> v;
for (int i = 0; i < k; i++) {
// If current row is not present,
// subtract r from ans
if (row[arr[i][0]]) {
ans -= r;
c--;
row[arr[i][0]] = false;
}
// If current column is not present,
// subtract c from ans and
// decrement value of r by 1.
if (col[arr[i][1]]) {
ans -= c;
r--;
col[arr[i][1]] = false;
}
v.push_back(ans);
}
return v;
}
// Driver code
int main()
{
int N = 3, Q = 3;
vector<vector<int> > arr
= { { 2, 2 }, { 2, 3 }, { 3, 2 } };
vector<long long int> ans = countZero(N, Q, arr);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
Java
// Java code to implement the above approach.
import java.util.*;
class GFG{
static Vector<Integer> countZero(
int n, int k,
int [][] arr)
{
int ans = n, r = n, c = n;
// for declaring n*n matrix
ans *= ans;
boolean []row = new boolean[n+1];
Arrays.fill(row, true);
boolean []col = new boolean[n+1];
Arrays.fill(col, true);
Vector<Integer> v = new Vector<Integer>();
for (int i = 0; i < k; i++) {
// If current row is not present,
// subtract r from ans
if (row[arr[i][0]]) {
ans -= r;
c--;
row[arr[i][0]] = false;
}
// If current column is not present,
// subtract c from ans and
// decrement value of r by 1.
if (col[arr[i][1]]) {
ans -= c;
r--;
col[arr[i][1]] = false;
}
v.add(ans);
}
return v;
}
// Driver code
public static void main(String[] args)
{
int N = 3, Q = 3;
int [][] arr
= { { 2, 2 }, { 2, 3 }, { 3, 2 } };
Vector<Integer> ans = countZero(N, Q, arr);
for (int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i)+ " ");
}
System.out.println();
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach def countZero(n, k, arr) : ans = n r = n c = n # for declaring n*n matrix ans *= ans row = [True] * (n + 1) col = [True] * (n + 1) v= [[]] for i in range(k): # If current row is not present, # subtract r from ans if (row[arr[i][0]]) : ans -= r c -= 1 row[arr[i][0]] = False # If current column is not present, # subtract c from ans and # decrement value of r by 1. if (col[arr[i][1]]) : ans -= c r -= 1 col[arr[i][1]] = False v.append(ans) return v # Driver code N = 3 Q = 3 arr = [[ 2, 2 ], [ 2, 3 ], [ 3, 2 ]] ans = countZero(N, Q, arr) for i in range(1, len(ans)): print(ans[i], end = " ") # This code is contributed by code_hunt.
C#
// C# code to implement the above approach.
using System;
using System.Collections;
class GFG {
static ArrayList countZero(int n, int k, int[, ] arr)
{
int ans = n, r = n, c = n;
// for declaring n*n matrix
ans *= ans;
ArrayList row = new ArrayList(n + 1);
ArrayList col = new ArrayList(n + 1);
for (int i = 0; i < n + 1; i++) {
row.Add(1);
col.Add(1);
}
ArrayList v = new ArrayList();
for (int i = 0; i < k; i++) {
// If current row is not present,
// subtract r from ans
if ((int)row[arr[i, 0]] == 1) {
ans -= r;
c--;
row[arr[i, 0]] = 0;
}
// If current column is not present,
// subtract c from ans and
// decrement value of r by 1.
if ((int)col[arr[i, 1]] == 1) {
ans -= c;
r--;
col[arr[i, 1]] = 0;
}
v.Add(ans);
}
return v;
}
// Driver code
public static void Main()
{
int N = 3, Q = 3;
int[, ] arr = { { 2, 2 }, { 2, 3 }, { 3, 2 } };
ArrayList ans = countZero(N, Q, arr);
for (int i = 0; i < ans.Count; i++) {
Console.Write(ans[i] + " ");
}
Console.WriteLine();
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
function countZero(n, k, arr)
{
let ans = n, r = n, c = n;
// for declaring n*n matrix
ans *= ans;
let row = new Array(n + 1).fill(true), col = new Array(n + 1).fill(true);
let v = [];
for (let i = 0; i < k; i++) {
// If current row is not present,
// subtract r from ans
if (row[arr[i][0]]) {
ans -= r;
c--;
row[arr[i][0]] = false;
}
// If current column is not present,
// subtract c from ans and
// decrement value of r by 1.
if (col[arr[i][1]]) {
ans -= c;
r--;
col[arr[i][1]] = false;
}
v.push(ans);
}
return v;
}
// Driver code
let N = 3, Q = 3;
let
arr = [[2, 2], [2, 3], [3, 2]];
let ans = countZero(N, Q, arr);
for (let i = 0; i < ans.length; i++) {
document.write(ans[i] + ' ');
}
document.write('<br>')
// This code is contributed by Potta Lokesh
</script>
4 2 1
Complejidad de tiempo: O(K)
Complejidad de espacio: O(N)
Publicación traducida automáticamente
Artículo escrito por vikramramwani2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA