Dada una array binaria (que contiene solo 0 y 1) de orden n×n. Todas las filas ya están ordenadas. Necesitamos encontrar el número de fila con el número máximo de 1s. Además, encuentre el número de 1 en esa fila.
Nota: en caso de empate, escriba el número de fila más pequeño.
Ejemplos:
Input : mat[3][3] = {0, 0, 1,
0, 1, 1,
0, 0, 0}
Output : Row number = 2, MaxCount = 2
Input : mat[3][3] = {1, 1, 1,
1, 1, 1,
0, 0, 0}
Output : Row number = 1, MaxCount = 3
Enfoque básico: recorrer toda la array y para cada fila encontrar el número de 1 y entre todos los que siguen actualizando el número de fila con el número máximo de 1. Este enfoque dará como resultado una complejidad de tiempo O (n ^ 2).
Mejor enfoque: podemos tener un mejor desempeño si tratamos de aplicar la búsqueda binaria para encontrar la posición del primer 1 en cada fila y, según eso, podemos encontrar el número de 1 de cada fila, ya que cada fila está ordenada. Esto dará como resultado una complejidad de tiempo O (nlogn).
Enfoque eficiente: comience con la esquina superior derecha con índice (1, n) e intente ir a la izquierda hasta llegar al último 1 en esa fila (columna j-ésima), ahora si cruzamos a la izquierda a esa fila, encontraremos 0, entonces cambie a la fila justo debajo, con la misma columna. Ahora su posición será (2, j) nuevamente en la segunda fila si el j-ésimo elemento es 1, intente ir a la izquierda hasta que encuentre el último 1; de lo contrario, en la segunda fila, si el j-ésimo elemento es 0, vaya a la siguiente fila. Entonces, finalmente, diga que si está en cualquier i-ésima fila y j-ésima columna, que es el índice del último 1 desde la derecha en esa fila, incremente i. Así que ahora, si tenemos Aij = 0 nuevamente, incremente i; de lo contrario, siga disminuyendo j hasta que encuentre el último 1 en esa fila en particular.
Ejemplo de ilustración:
Algoritmo:
for (int i=0, j=n-1; i<n;i++)
{
// find left most position of 1 in a row
// find 1st zero in a row
while (arr[i][j]==1)
{
row = i;
j--;
}
}
cout << "Row number =" << row+1;
cout << "MaxCount =" << n-j;
Implementación:
C++
// CPP program to find row with maximum 1
// in row sorted binary matrix
#include<bits/stdc++.h>
#define N 4
using namespace std;
// function for finding row with maximum 1
void findMax (int arr[][N])
{
int row = 0, i, j;
for (i=0, j=N-1; i<N;i++)
{
// find left most position of 1 in a row
// find 1st zero in a row
while (arr[i][j] == 1 && j >= 0)
{
row = i;
j--;
}
}
cout << "Row number = " << row+1;
cout << ", MaxCount = " << N-1-j;
}
// driver program
int main()
{
int arr[N][N] = {0, 0, 0, 1,
0, 0, 0, 1,
0, 0, 0, 0,
0, 1, 1, 1};
findMax(arr);
return 0;
}
Java
// Java program to find row with maximum 1
// in row sorted binary matrix
class GFG {
static final int N = 4;
// function for finding row with maximum 1
static void findMax(int arr[][]) {
int row = 0, i, j;
for (i = 0, j = N - 1; i < N; i++) {
// find left most position of 1 in
// a row find 1st zero in a row
while (j >= 0 && arr[i][j] == 1) {
row = i;
j--;
}
}
System.out.print("Row number = "
+ (row + 1));
System.out.print(", MaxCount = "
+ (N - 1 - j));
}
// Driver code
public static void main(String[] args) {
int arr[][] = {{0, 0, 0, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 1, 1, 1}};
findMax(arr);
}
}
// This code is contributed by Anant Agarwal.
Python3
# python program to find row with
# maximum 1 in row sorted binary
# matrix
N = 4
# function for finding row with
# maximum 1
def findMax (arr):
row = 0
j = N - 1
for i in range(0, N):
# find left most position
# of 1 in a row find 1st
# zero in a row
while (arr[i][j] == 1
and j >= 0):
row = i
j -= 1
print("Row number = " , row + 1,
", MaxCount = ", N - 1 - j)
# driver program
arr = [ [0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[0, 1, 1, 1] ]
findMax(arr)
# This code is contributed by Sam007
C#
// C# program to find row with maximum
// 1 in row sorted binary matrix
using System;
class GFG {
static int N = 4;
// function for finding row with maximum 1
static void findMax(int [,]arr)
{
int row = 0, i, j;
for (i = 0, j = N - 1; i < N; i++) {
// find left most position of 1 in
// a row find 1st zero in a row
while (arr[i,j] == 1 && j >= 0)
{
row = i;
j--;
}
}
Console.Write("Row number = " + (row + 1));
Console.Write(", MaxCount = " + (N - 1 - j));
}
// Driver code
public static void Main()
{
int [,]arr = {{0, 0, 0, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 1, 1, 1}};
findMax(arr);
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to find
// row with maximum 1
// in row sorted
// binary matrix
$N = 4;
// function for finding
// row with maximum 1
function findMax ($arr)
{
global $N;
$row = 0; $i;
$j=$N - 1;
for ($i = 0; $i < $N; $i++)
{
// find left most position
// of 1 in a row find 1st
// zero in a row
while ($arr[$i][$j] == 1 &&
$j >= 0)
{
$row = $i;
$j--;
}
}
echo "Row number = " , $row + 1;
echo ", MaxCount = " , $N - 1 - $j;
}
// Driver Code
$arr = array(array(0, 0, 0, 1),
array(0, 0, 0, 1),
array(0, 0, 0, 0),
array(0, 1, 1, 1));
findMax($arr);
// This code is contributed by vt_m.
?>
Javascript
<script>
// Javascript program to find row with maximum 1
// in row sorted binary matrix
var N = 4
// function for finding row with maximum 1
function findMax (arr)
{
var row = 0, i, j;
for (i=0, j=N-1; i<N;i++)
{
// find left most position of 1 in a row
// find 1st zero in a row
while (arr[i][j] == 1 && j >= 0)
{
row = i;
j--;
}
}
document.write( "Row number = " + (row+1));
document.write( ", MaxCount = " + (N-1-j));
}
// driver program
var arr = [[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[0, 1, 1, 1]];
findMax(arr);
</script>
Row number = 4, MaxCount = 3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA