Dada una array 2D que contiene solo ceros y unos, donde se ordena cada fila. La tarea es encontrar la fila con el número máximo de 0 y la fila con el número mínimo de 0.
Ejemplo:
Entrada: mat[][] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}}
Salida :
Fila con ceros mínimos: 3
Fila con ceros máximos: 4
Entrada: mat[][] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1 },
{0, 0, 0, 0}}
Salida:
Fila con ceros mínimos: 1
Fila con ceros máximos: 4
Enfoque simple: un método simple es hacer un recorrido por filas de la array, contar el número de 0 en cada fila y comparar el conteo con el máximo y el mínimo. Finalmente, devuelva el índice de la fila con un máximo de 0 y un mínimo de 0. La complejidad temporal de este método es O(M*N) donde M es un número de filas y N es un número de columnas en la array.
Enfoque eficiente: dado que cada fila está ordenada, podemos usar la búsqueda binaria para encontrar el recuento de 0 en cada fila. La idea es encontrar el índice de primera instancia de 1 en cada fila.
El conteo de 0s en esa fila será:
- Si existe 1 en la fila, el recuento de 0 será igual al índice del primer 1 en la fila considerando la indexación basada en cero.
- Si 1 no existe en la fila, entonces el recuento de 0 será N, que es el número total de columnas en la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
// Function to find the index of first 1
// in the binary array arr[]
int first(bool arr[], int low, int high)
{
if (high >= low) {
// Get the middle index
int mid = low + (high - low) / 2;
// Check if the element at middle index is first 1
if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1)
return mid;
// If the element is 0, recur for right side
else if (arr[mid] == 0)
return first(arr, (mid + 1), high);
// If element is not first 1, recur for left side
else
return first(arr, low, (mid - 1));
}
return -1;
}
// Function to print rows with maximum
// and minimum number of zeroes
void rowWith0s(bool mat[R][C])
{
// Initialize max values
int max_row_index = 0, max = INT_MIN;
// Initialize min values
int min_row_index = 0, min = INT_MAX;
// Traverse for each row and count number of 0s
// by finding the index of first 1
int i, index;
for (i = 0; i < R; i++) {
index = first(mat[i], 0, C - 1);
int cntZeroes = 0;
// If index = -1, that is there is no 1
// in the row, count of zeroes will be C
if (index == -1) {
cntZeroes = C;
}
// Else, count of zeroes will be index
// of first 1
else {
cntZeroes = index;
}
// Find max row index
if (max < cntZeroes) {
max = cntZeroes;
max_row_index = i;
}
// Find min row index
if (min > cntZeroes) {
min = cntZeroes;
min_row_index = i;
}
}
cout << "Row with min 0s: " << min_row_index + 1;
cout << "\nRow with max 0s: " << max_row_index + 1;
}
// Driver code
int main()
{
bool mat[R][C] = { { 0, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 0, 0, 0, 0 } };
rowWith0s(mat);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG
{
static int R = 4;
static int C = 4;
// Function to find the index of first 1
// in the binary array arr[]
static int first(int arr[], int low, int high)
{
if (high >= low)
{
// Get the middle index
int mid = low + (high - low) / 2;
// Check if the element at middle index is first 1
if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1)
return mid;
// If the element is 0, recur for right side
else if (arr[mid] == 0)
return first(arr, (mid + 1), high);
// If element is not first 1, recur for left side
else
return first(arr, low, (mid - 1));
}
return -1;
}
// Function to print rows with maximum
// and minimum number of zeroes
static void rowWith0s(int mat[][])
{
// Initialize max values
int max_row_index = 0, max = Integer.MIN_VALUE;
// Initialize min values
int min_row_index = 0, min = Integer.MAX_VALUE;
// Traverse for each row and count number of 0s
// by finding the index of first 1
int i, index;
for (i = 0; i < R; i++)
{
index = first(mat[i], 0, C - 1);
int cntZeroes = 0;
// If index = -1, that is there is no 1
// in the row, count of zeroes will be C
if (index == -1)
{
cntZeroes = C;
}
// Else, count of zeroes will be index
// of first 1
else
{
cntZeroes = index;
}
// Find max row index
if (max < cntZeroes)
{
max = cntZeroes;
max_row_index = i;
}
// Find min row index
if (min > cntZeroes)
{
min = cntZeroes;
min_row_index = i;
}
}
System.out.println ("Row with min 0s: " + (min_row_index + 1));
System.out.println ("Row with max 0s: " + (max_row_index + 1));
}
// Driver code
public static void main (String[] args)
{
int mat[][] = { { 0, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 0, 0, 0, 0 } };
rowWith0s(mat);
}
}
// This code is contributed by ajit.
Python3
# Python3 implementation of the approach
import sys
R = 4
C = 4
# Function to find the index of first 1
# in the binary array arr[]
def first(arr, low, high) :
if (high >= low) :
# Get the middle index
mid = low + (high - low) // 2;
# Check if the element at middle index is first 1
if ((mid == 0 or arr[mid - 1] == 0) and arr[mid] == 1) :
return mid;
# If the element is 0, recur for right side
elif (arr[mid] == 0) :
return first(arr, (mid + 1), high);
# If element is not first 1, recur for left side
else :
return first(arr, low, (mid - 1));
return -1;
# Function to print rows with maximum
# and minimum number of zeroes
def rowWith0s(mat) :
# Initialize max values
row_index = 0; max = -(sys.maxsize - 1);
# Initialize min values
min_row_index = 0; min = sys.maxsize;
# Traverse for each row and count number of 0s
# by finding the index of first 1
for i in range(R) :
index = first(mat[i], 0, C - 1);
cntZeroes = 0;
# If index = -1, that is there is no 1
# in the row, count of zeroes will be C
if (index == -1) :
cntZeroes = C;
# Else, count of zeroes will be index
# of first 1
else :
cntZeroes = index;
# Find max row index
if (max < cntZeroes) :
max = cntZeroes;
max_row_index = i;
# Find min row index
if (min > cntZeroes) :
min = cntZeroes;
min_row_index = i;
print("Row with min 0s:",min_row_index + 1);
print("Row with max 0s:", max_row_index + 1);
# Driver code
if __name__ == "__main__" :
mat = [
[ 0, 0, 0, 1 ],
[ 0, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 0, 0, 0, 0 ]
];
rowWith0s(mat);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int R = 4;
static int C = 4;
// Function to find the index of first 1
// in the binary array arr[]
static int first(int []arr, int low, int high)
{
if (high >= low)
{
// Get the middle index
int mid = low + (high - low) / 2;
// Check if the element at middle index is first 1
if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1)
return mid;
// If the element is 0, recur for right side
else if (arr[mid] == 0)
return first(arr, (mid + 1), high);
// If element is not first 1, recur for left side
else
return first(arr, low, (mid - 1));
}
return -1;
}
// Function to print rows with maximum
// and minimum number of zeroes
static void rowWith0s(int [,]mat)
{
// Initialize max values
int max_row_index = 0, max = int.MinValue;
// Initialize min values
int min_row_index = 0, min = int.MaxValue;
// Traverse for each row and count number of 0s
// by finding the index of first 1
int i, index;
for (i = 0; i < R; i++)
{
index = first(GetRow(mat,i), 0, C - 1);
int cntZeroes = 0;
// If index = -1, that is there is no 1
// in the row, count of zeroes will be C
if (index == -1)
{
cntZeroes = C;
}
// Else, count of zeroes will be index
// of first 1
else
{
cntZeroes = index;
}
// Find max row index
if (max < cntZeroes)
{
max = cntZeroes;
max_row_index = i;
}
// Find min row index
if (min > cntZeroes)
{
min = cntZeroes;
min_row_index = i;
}
}
Console.WriteLine ("Row with min 0s: " + (min_row_index + 1));
Console.WriteLine ("Row with max 0s: " + (max_row_index + 1));
}
public static int[] GetRow(int[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver code
public static void Main (String[] args)
{
int [,]mat = { { 0, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 0, 0, 0, 0 } };
rowWith0s(mat);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript implementation of the approach
var R = 4;
var C = 4;
// Function to find the index of first 1
// in the binary array arr
function first(arr , low , high)
{
if (high >= low)
{
// Get the middle index
var mid = low + parseInt((high - low) / 2);
// Check if the element at middle
// index is first 1
if ((mid == 0 || arr[mid - 1] == 0) &&
arr[mid] == 1)
return mid;
// If the element is 0, recur for right side
else if (arr[mid] == 0)
return first(arr, (mid + 1), high);
// If element is not first 1,
// recur for left side
else
return first(arr, low, (mid - 1));
}
return -1;
}
// Function to print rows with maximum
// and minimum number of zeroes
function rowWith0s(mat)
{
// Initialize max values
var max_row_index = 0, max = Number.MIN_VALUE;
// Initialize min values
var min_row_index = 0, min = Number.MAX_VALUE;
// Traverse for each row and count number of 0s
// by finding the index of first 1
var i, index;
for (i = 0; i < R; i++)
{
index = first(mat[i], 0, C - 1);
var cntZeroes = 0;
// If index = -1, that is there is no 1
// in the row, count of zeroes will be C
if (index == -1)
{
cntZeroes = C;
}
// Else, count of zeroes will be index
// of first 1
else
{
cntZeroes = index;
}
// Find max row index
if (max < cntZeroes)
{
max = cntZeroes;
max_row_index = i;
}
// Find min row index
if (min > cntZeroes)
{
min = cntZeroes;
min_row_index = i;
}
}
document.write("Row with min 0s: " +
(min_row_index + 1)+"<br/>");
document.write("Row with max 0s: " +
(max_row_index + 1));
}
// Driver code
var mat = [ [ 0, 0, 0, 1 ],
[ 0, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 0, 0, 0, 0 ] ];
rowWith0s(mat);
// This code contributed by Rajput-Ji
</script>
Producción:
Row with min 0s: 3 Row with max 0s: 4
Complejidad de tiempo: O(R*logC), ya que estamos usando un ciclo para atravesar R tiempos y en cada recorrido estamos llamando primero a la función, lo que costará O(logC) tiempo ya que estamos usando la búsqueda binaria.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.