Dada una array arr[][] de tamaño N * M , la tarea es imprimir la array después de eliminar todas las filas y columnas de la array que consta de 0 s solamente.
Ejemplos:
Entrada: arr[][] ={ { 1, 1, 0, 1 }, { 0, 0, 0, 0 }, { 1, 1, 0, 1}, { 0, 1, 0, 1 } }
Salida :
111
111
011
Explicación:
Inicialmente, la array es la siguiente:
arr[][] = { { 1, 1, 0, 1 },
{ 0, 0, 0, 0 },
{ 1, 1, 0, 1 } ,
{ 0, 1, 0, 1 } }
Al eliminar la segunda fila, la array se modifica a:
arr[][] = { { 1, 1, 0, 1 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } }
Al eliminar la tercera columna, la array se modifica a:
arr[][] = { { 1, 1, 1 },
{ 1, 1, 1 },
{ 0, 1, 1 } }Entrada: arr={{0, 1}, {0, 1}}
Salida:
1
1
Enfoque: La idea es contar el número de 0 en todas las filas y columnas de la array y verificar si alguna fila o columna consta solo de 0 o no. Si se determina que es cierto, elimine esas filas o las columnas de la array. Siga los pasos a continuación para resolver el problema:
- Recorre la array y cuenta 1 s en filas y columnas.
- Ahora, recorra el bucle nuevamente y verifique lo siguiente:
- Si se encuentra que el conteo de 1 s es 0 para cualquier fila, omita esa fila.
- Si se encuentra que el conteo de 1 s es mayor que 0 para cualquier columna, imprima ese elemento.
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;
// Function to remove the rows or columns from
// the matrix which contains all 0s elements
void removeZeroRowCol(vector<vector<int> >& arr)
{
// Stores count of rows
int n = arr.size();
// col[i]: Stores count of 0s
// in current column
int col[n + 1] = { 0 };
// row[i]: Stores count of 0s
// in current row
int row[n + 1] = { 0 };
// Traverse the matrix
for (int i = 0; i < n; ++i) {
// Stores count of 0s
// in current row
int count = 0;
for (int j = 0; j < n; ++j) {
// Update col[j]
col[j] += (arr[i][j] == 1);
// Update count
count += (arr[i][j] == 1);
}
// Update row[i]
row[i] = count;
}
// Traverse the matrix
for (int i = 0; i < n; ++i) {
// If all elements of
// current row is 0
if (row[i] == 0) {
continue;
}
for (int j = 0; j < n; ++j) {
// If all elements of
// current column is 0
if (col[j] != 0)
cout << arr[i][j];
}
cout << "\n";
}
}
// Driver Code
int main()
{
vector<vector<int> > arr = { { 1, 1, 0, 1 },
{ 0, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } };
// Function Call
removeZeroRowCol(arr);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to remove the rows or columns from
// the matrix which contains all 0s elements
static void removeZeroRowCol(int arr[][])
{
// Stores count of rows
int n = arr.length;
// col[i]: Stores count of 0s
// in current column
int col[] = new int[n + 1];
// row[i]: Stores count of 0s
// in current row
int row[] = new int[n + 1];
// Traverse the matrix
for(int i = 0; i < n; ++i)
{
// Stores count of 0s
// in current row
int count = 0;
for(int j = 0; j < n; ++j)
{
if (arr[i][j] == 1)
// Update col[j]
col[j] += 1;
else
col[j] += 0;
if (arr[i][j] == 1)
// Update count
count += 1;
else
count += 0;
}
// Update row[i]
row[i] = count;
}
// Traverse the matrix
for(int i = 0; i < n; ++i)
{
// If all elements of
// current row is 0
if (row[i] == 0)
{
continue;
}
for(int j = 0; j < n; ++j)
{
// If all elements of
// current column is 0
if (col[j] != 0)
System.out.print(arr[i][j]);
}
System.out.println();
}
}
// Driver Code
public static void main (String[] args)
{
int arr[][] = { { 1, 1, 0, 1 },
{ 0, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } };
// Function Call
removeZeroRowCol(arr);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to remove the rows or columns from # the matrix which contains all 0s elements def removeZeroRowCol(arr) : # Stores count of rows n = len(arr) # col[i]: Stores count of 0s # in current column col = [0] * (n + 1) # row[i]: Stores count of 0s # in current row row = [0] * (n + 1) # Traverse the matrix for i in range(n) : # Stores count of 0s # in current row count = 0 for j in range(n) : # Update col[j] col[j] += (arr[i][j] == 1) # Update count count += (arr[i][j] == 1) # Update row[i] row[i] = count # Traverse the matrix for i in range(n) : # If all elements of # current row is 0 if (row[i] == 0) : continue for j in range(n) : # If all elements of # current column is 0 if (col[j] != 0) : print(arr[i][j], end = "") print() arr = [ [ 1, 1, 0, 1 ], [ 0, 0, 0, 0 ], [ 1, 1, 0, 1 ], [ 0, 1, 0, 1 ] ] # Function Call removeZeroRowCol(arr) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
class GFG{
// Function to remove the rows or columns from
// the matrix which contains all 0s elements
static void removeZeroRowCol(int[,] arr)
{
// Stores count of rows
int n = arr.GetLength(0);
// col[i]: Stores count of 0s
// in current column
int[] col = new int[n + 1];
// row[i]: Stores count of 0s
// in current row
int[] row = new int[n + 1];
// Traverse the matrix
for(int i = 0; i < n ; ++i)
{
// Stores count of 0s
// in current row
int count = 0;
for(int j = 0; j < n ; ++j)
{
if (arr[i, j] == 1)
// Update col[j]
col[j] += 1;
else
col[j] += 0;
if (arr[i, j] == 1)
// Update count
count += 1;
else
count += 0;
}
// Update row[i]
row[i] = count;
}
// Traverse the matrix
for(int i = 0; i < n; ++i)
{
// If all elements of
// current row is 0
if (row[i] == 0)
{
continue;
}
for(int j = 0; j < n; ++j)
{
// If all elements of
// current column is 0
if (col[j] != 0)
Console.Write(arr[i, j]);
}
Console.WriteLine();
}
}
// Driver Code
public static void Main (String[] args)
{
int[,] arr = { { 1, 1, 0, 1 },
{ 0, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } };
// Function Call
removeZeroRowCol(arr);
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to remove the rows or columns from
// the matrix which contains all 0s elements
function removeZeroRowCol(arr)
{
// Stores count of rows
let n = arr.length;
// col[i]: Stores count of 0s
// in current column
let col = Array.from({length: n+1}, (_, i) => 0);
// row[i]: Stores count of 0s
// in current row
let row = Array.from({length: n+1}, (_, i) => 0);
// Traverse the matrix
for(let i = 0; i < n; ++i)
{
// Stores count of 0s
// in current row
let count = 0;
for(let j = 0; j < n; ++j)
{
if (arr[i][j] == 1)
// Update col[j]
col[j] += 1;
else
col[j] += 0;
if (arr[i][j] == 1)
// Update count
count += 1;
else
count += 0;
}
// Update row[i]
row[i] = count;
}
// Traverse the matrix
for(let i = 0; i < n; ++i)
{
// If all elements of
// current row is 0
if (row[i] == 0)
{
continue;
}
for(let j = 0; j < n; ++j)
{
// If all elements of
// current column is 0
if (col[j] != 0)
document.write(arr[i][j]);
}
document.write("<br/>");
}
}
// Driver Code
let arr = [[ 1, 1, 0, 1 ],
[ 0, 0, 0, 0 ],
[ 1, 1, 0, 1 ],
[ 0, 1, 0, 1 ]];
// Function Call
removeZeroRowCol(arr);
// This code is contributed by souravghosh0416.
</script>
Producción
111 111 011
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Otro enfoque eficiente: la idea es marcar todas las filas y columnas que contienen solo ceros con algún otro número entero especial (un valor que no está presente en la array) para identificar que no necesitamos esa fila o columna en particular y siempre que alcancemos Mientras al iterar sobre la array en ese entero en particular, omitimos esa celda porque asumimos que la celda se eliminó al eliminar la fila o columna que tiene todos ceros.
Siga los siguientes pasos para implementar la idea:
- Repita todas las filas una por una y verifique si esa fila en particular contiene todos los ceros o no.
Si una fila en particular contiene todos los ceros, complete un entero especial para marcar que la fila contiene todos los ceros. - Repita todas las columnas una por una y verifique si esa columna en particular contiene todos los ceros o no.
Si una columna en particular contiene solo ceros, complete un entero especial para marcar que las columnas contienen solo ceros. - Itere sobre la array y verifique si alguna celda en particular está marcada con un número entero especial.
En caso afirmativo, omita esa celda.
De lo contrario, imprima esa celda.
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;
// Function to mark all row and column
// to special integer which contains all zeros
void removeZeroRowCol(vector<vector<int> >& A)
{
int i, j, m, n;
m = A.size();
if (m != 0)
n = A[0].size();
// Traversing by row
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
// If found that the complete row do
// not contain only zeros
if (A[i][j] == 1)
break;
}
// If found that the complete row
// contain zero
if (j == n) {
for (j = 0; j < n; j++)
A[i][j] = -1;
}
}
// Traversing by column
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
// If found that the complete column
// do not contain all zeros
if (A[j][i] == 1)
break;
}
// If found that the complete column
// contain only zeros
if (j == n) {
for (j = 0; j < n; j++)
A[j][i] = -1;
}
}
}
// Function to print the matrix
void print(vector<vector<int> >& A)
{
int i, j, m, n;
m = A.size();
if (m != 0)
n = A[0].size();
// Taking a flag which helps us in printing
// the matrix because if we found that the above
// row is contain only zero then we won't go to next
// line otherwise there will be space between
// two consecutive rows
bool flag = false;
// Iterating over matrix
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (A[i][j] != -1) {
cout << A[i][j];
// Making flag true if row get
// printed
flag = true;
}
}
// If row got printed then moving to the
// next line
if (flag) {
cout << endl;
flag = !flag;
}
}
}
// Driver code
int main()
{
// Initializing matrix
vector<vector<int> > arr{ { 1, 1, 0, 1 },
{ 0, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } };
// Function calling
removeZeroRowCol(arr);
// Function to print the matrix
print(arr);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Java code to implement the above approach
// Function to mark all row and column
// to special integer which contains all zeros
static void removeZeroRowCol(int[][] A)
{
int i = 0, j = 0, m = A.length, n = 0;
if (m != 0)
n = A[0].length;
// Traversing by row
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
// If found that the complete row do
// not contain only zeros
if (A[i][j] == 1)
break;
}
// If found that the complete row
// contain zero
if (j == n) {
for (j = 0; j < n; j++)
A[i][j] = -1;
}
}
// Traversing by column
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
// If found that the complete column
// do not contain all zeros
if (A[j][i] == 1)
break;
}
// If found that the complete column
// contain only zeros
if (j == n) {
for (j = 0; j < n; j++)
A[j][i] = -1;
}
}
}
private static void e() {
}
// Function to print the matrix
static void print(int[][] A)
{
int i = 0, j = 0, m = 0, n = 0;
m = A.length;
if (m != 0)
n = A[0].length;
// Taking a flag which helps us in printing
// the matrix because if we found that the above
// row is contain only zero then we won't go to next
// line otherwise there will be space between
// two consecutive rows
boolean flag = false;
// Iterating over matrix
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (A[i][j] != -1) {
System.out.print(A[i][j]);
// Making flag true if row get
// printed
flag = true;
}
}
// If row got printed then moving to the
// next line
if (flag) {
System.out.println();
flag = !flag;
}
}
}
// Driver Code
public static void main(String args[])
{
// Initializing matrix
int[][] arr = { { 1, 1, 0, 1 },
{ 0, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } };
// Function calling
removeZeroRowCol(arr);
// Function to print the matrix
print(arr);
}
}
// This code is contributed by shinjanpatra
Python3
# Python code to implement the above approach # Function to mark all row and column # to special integer which contains all zeros def removeZeroRowCol(A): m = len(A) if (m != 0): n = len(A[0]) i,j = 0,0 # Traversing by row for i in range(m): for j in range(n): # If found that the complete row do # not contain only zeros if (A[i][j] == 1): break # If found that the complete row # contain zero if (j == n-1): for j in range(n): A[i][j] = -1 # Traversing by column for i in range(m): for j in range(n): # If found that the complete column # do not contain all zeros if (A[j][i] == 1): break # If found that the complete column # contain only zeros if (j == n-1): for j in range(n): A[j][i] = -1 # Function to print the matrix def Print(A): m = len(A) if (m != 0): n = len(A[0]) # Taking a flag which helps us in printing # the matrix because if we found that the above # row is contain only zero then we won't go to next # line otherwise there will be space between # two consecutive rows flag = False # Iterating over matrix for i in range(m): for j in range(n): if (A[i][j] != -1): print(A[i][j],end="") # Making flag true if row get # printed flag = True # If row got printed then moving to the # next line if (flag): print() flag = False if (flag == True) else True # Driver code # Initializing matrix arr = [ [ 1, 1, 0, 1 ], [ 0, 0, 0, 0 ], [ 1, 1, 0, 1 ], [ 0, 1, 0, 1 ] ] # Function calling removeZeroRowCol(arr) # Function to print the matrix Print(arr) # This code is contributed by shinjanpatra
Producción
111 111 011
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA