Dada una array binaria , mat[][] de dimensiones N * M , la tarea es maximizar el recuento de filas que consisten solo en elementos iguales seleccionando cualquier columna de la array y volteando todos los elementos de esa columna en cada operación. Imprime el número máximo de filas que se pueden hacer para formar elementos iguales.
Ejemplos:
Entrada: mat[][] = { { 0, 1, 0, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 1, 0 } }
Salida: 2
Explicación:
Seleccione la segunda columna y voltee todos los elementos de esa columna para modificar mat[][] a { { 0, 0, 0, 0, 1 }, { 1, 0, 0, 1, 1 }, { 1, 1 , 1, 1, 0 } }
Seleccione la quinta columna y voltee todos los elementos de esa columna para modificar mat[][] a { { 0, 0, 0, 0, 0 }, { 1, 0, 0, 1 , 0 }, { 1, 1, 1, 1, 1 } }
Dado que todos los elementos de la 1 ra fila y la 3 ra fila de la array son iguales y también es el número máximo de filas que se pueden hacer para contener elementos iguales solo, la salida requerida es 2.
Entrada: mat[][] = { {0, 0}, {0, 1} }
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver este problema es contar el número de filas que contienen elementos iguales únicamente, para todas las formas posibles de seleccionar una combinación de columnas y voltear sus elementos. Finalmente, imprima el conteo máximo obtenido para cualquiera de las combinaciones anteriores.
Complejidad de Tiempo: O(N * M * 2 M )
Espacio Auxiliar: O(N * M)
Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en el hecho de que, si una fila es el complemento de 1 de la otra fila o ambas filas son iguales, entonces solo ambas filas contendrán elementos iguales solo realizando el operaciones dadas.
Ilustración:
Consideremos la siguiente array:
1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 0 En la array anterior, las filas 1 y 2 son complemento a 1 entre sí, y las filas 5 y 4 son complemento a 1 entre sí.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntMaxRows , para almacenar la cantidad máxima de filas que constan solo de elementos iguales.
- Inicialice un Map , digamos mp , para almacenar todas las filas posibles de la array.
- Recorra cada fila de la array y guárdela en el Mapa .
- Recorra cada fila de la array usando la variable fila . Calcule el complemento de fila de 1 y actualice cntMaxRows = max(cntMaxRows, mp[row] + mp[1’s_comp_row])
- Finalmente, imprima el valor de cntMaxRows .
A continuación se muestra la implementación de nuestro enfoque:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number
// of rows containing all equal elements
int maxEqrows(vector<vector<int> >& mat,
int N, int M)
{
// Store each row of the matrix
map<vector<int>, int> mp;
// Traverse each row of the matrix
for (int i = 0; i < N; i++) {
// Update frequency of
// current row
mp[mat[i]]++;
}
// Stores maximum count of rows
// containing all equal elements
int cntMaxRows = 0;
// Traverse each row of the matrix
for (int i = 0; i < N; i++) {
// Stores 1's complement
// of the current row
vector<int> onesCompRow(M, 0);
// Traverse current row
// of the given matrix
for (int j = 0; j < M; j++) {
// Stores 1s complement of
// mat[i][j]
onesCompRow[j]
= (mat[i][j] ^ 1);
}
// Update cntMaxRows
cntMaxRows = max(cntMaxRows,
mp[mat[i]] + mp[onesCompRow]);
}
return cntMaxRows;
}
// Driver Code
int main()
{
vector<vector<int> > mat
= { { 0, 1, 0, 0, 1 },
{ 1, 1, 0, 1, 1 },
{ 1, 0, 1, 1, 0 } };
// Stores count of rows
int N = mat.size();
// Stores count of columns
int M = mat[0].size();
cout << maxEqrows(mat, N, M);
}
Java
// Java program to implement
import java.util.*;
class GFG
{
// Function to find the maximum number
// of rows containing all equal elements
static int maxEqrows(Vector<Vector<Integer>> mat,
int N, int M)
{
// Store each row of the matrix
HashMap<Vector<Integer>, Integer> mp = new HashMap<>();
// Traverse each row of the matrix
for (int i = 0; i < N; i++)
{
// Update frequency of
// current row
if(mp.containsKey(mat.get(i)))
{
mp.put(mat.get(i), mp.get(mat.get(i)) + 1);
}
else
{
mp.put(mat.get(i), 1);
}
}
// Stores maximum count of rows
// containing all equal elements
int cntMaxRows = 0;
// Traverse each row of the matrix
for (int i = 0; i < N; i++)
{
// Stores 1's complement
// of the current row
Vector<Integer> onesCompRow = new Vector<Integer>();
for(int j = 0; j < M; j++)
{
onesCompRow.add(0);
}
// Traverse current row
// of the given matrix
for (int j = 0; j < M; j++)
{
// Stores 1s complement of
// mat[i][j]
onesCompRow.set(j, mat.get(i).get(j) ^ 1);
}
// Update cntMaxRows
if(!mp.containsKey(mat.get(i)))
{
cntMaxRows = Math.max(cntMaxRows, mp.get(onesCompRow));
}
else if(!mp.containsKey(onesCompRow))
{
cntMaxRows = Math.max(cntMaxRows, mp.get(mat.get(i)));
}
else
{
cntMaxRows = Math.max(cntMaxRows, mp.get(mat.get(i)) +
mp.get(onesCompRow));
}
}
return cntMaxRows;
}
// Driver code
public static void main(String[] args)
{
Vector<Vector<Integer>> mat = new Vector<Vector<Integer>>();
mat.add(new Vector<Integer>());
mat.add(new Vector<Integer>());
mat.add(new Vector<Integer>());
mat.get(0).add(0);
mat.get(0).add(1);
mat.get(0).add(0);
mat.get(0).add(0);
mat.get(0).add(1);
mat.get(1).add(1);
mat.get(1).add(1);
mat.get(1).add(0);
mat.get(1).add(1);
mat.get(1).add(1);
mat.get(2).add(1);
mat.get(2).add(0);
mat.get(2).add(1);
mat.get(2).add(1);
mat.get(2).add(0);
// Stores count of rows
int N = mat.size();
// Stores count of columns
int M = mat.get(0).size();
System.out.println(maxEqrows(mat, N, M));
}
}
// This code is contributed by divyesh072019
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the maximum number
// of rows containing all equal elements
static int maxEqrows(List<List<int>> mat, int N, int M)
{
// Store each row of the matrix
Dictionary<List<int>, int> mp = new Dictionary<List<int>, int>();
// Traverse each row of the matrix
for (int i = 0; i < N; i++) {
// Update frequency of
// current row
if(mp.ContainsKey(mat[i]))
{
mp[mat[i]]++;
}
else{
mp[mat[i]] = 1;
}
}
// Stores maximum count of rows
// containing all equal elements
int cntMaxRows = 0;
// Traverse each row of the matrix
for (int i = 0; i < N; i++) {
// Stores 1's complement
// of the current row
List<int> onesCompRow = new List<int>();
for(int j = 0; j < M; j++)
{
onesCompRow.Add(0);
}
// Traverse current row
// of the given matrix
for (int j = 0; j < M; j++) {
// Stores 1s complement of
// mat[i][j]
onesCompRow[j] = (mat[i][j] ^ 1);
}
// Update cntMaxRows
if(!mp.ContainsKey(mat[i]))
{
cntMaxRows = Math.Max(cntMaxRows, mp[onesCompRow] + 1);
}
else if(!mp.ContainsKey(onesCompRow))
{
cntMaxRows = Math.Max(cntMaxRows, mp[mat[i]] + 1);
}
else{
cntMaxRows = Math.Max(cntMaxRows, mp[mat[i]] + mp[onesCompRow] + 1);
}
}
return cntMaxRows;
}
// Driver code
static void Main() {
List<List<int>> mat = new List<List<int>>();
mat.Add(new List<int> { 0, 1, 0, 0, 1 });
mat.Add(new List<int> { 1, 1, 0, 1, 1 });
mat.Add(new List<int> { 1, 0, 1, 1, 0 });
// Stores count of rows
int N = mat.Count;
// Stores count of columns
int M = mat[0].Count;
Console.WriteLine(maxEqrows(mat, N, M));
}
}
// This code is contributed by divyeshrabadiya07
2
Complejidad temporal: O(N * M)
Espacio auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA