Dada una array booleana 2D, donde se ordena cada fila. Encuentre la fila con el número máximo de 1s.
Ejemplo:
Input matrix 0 1 1 1 0 0 1 1 1 1 1 1 // this row has maximum 1s 0 0 0 0 Output: 2
Un método simple es hacer un recorrido por filas de la array, contar el número de 1 en cada fila y comparar el conteo con max. Finalmente, devuelva el índice de la fila con un máximo de 1. La complejidad temporal de este método es O(m*n) donde m es el número de filas y n es el número de columnas en la array.
Implementación:
C++
// CPP program to find the row
// with maximum number of 1s
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
// Function that returns index of row
// with maximum number of 1s.
int rowWithMax1s(bool mat[R][C]) {
// code here
int rowIndex = -1 ;
int maxCount = 0 ;
for(int i = 0 ; i < R ; i++){
int count = 0 ;
for(int j = 0 ; j < C ; j++ ){
if(mat[i][j] == 1){
count++ ;
}
}
if(count > maxCount){
maxCount = count ;
rowIndex = i ;
}
}
return rowIndex ;
}
// Driver Code
int main()
{
bool mat[R][C] = { {0, 0, 0, 1},
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}};
cout << "Index of row with maximum 1s is " << rowWithMax1s(mat);
return 0;
}
C
// C program to find the row with maximum number of 1s.
#include<stdio.h>
#include<stdbool.h>
#define R 4
#define C 4
// Function that returns index of row
// with maximum number of 1s.
int rowWithMax1s(bool mat[R][C]) {
int indexOfRowWithMax1s = -1 ;
int maxCount = 0 ;
// Visit each row.
// Count number of 1s.
/* If count is more that the maxCount then update the maxCount
and store the index of current row in indexOfRowWithMax1s variable. */
for(int i = 0 ; i < R ; i++){
int count = 0 ;
for(int j = 0 ; j < C ; j++ ){
if(mat[i][j] == 1){
count++ ;
}
}
if(count > maxCount){
maxCount = count ;
indexOfRowWithMax1s = i ;
}
}
return indexOfRowWithMax1s ;
}
// Driver Code
int main()
{
bool mat[R][C] = { {0, 0, 0, 1},
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}};
int indexOfRowWithMax1s = rowWithMax1s(mat);
printf("Index of row with maximum 1s is %d",indexOfRowWithMax1s);
return 0;
}
// This code is contributed by Rohit_Dwivedi
Java
// Java program for the above approach
import java.util.*;
class GFG {
static int R = 4 ;
static int C = 4 ;
// Function to find the index of first index
// of 1 in a boolean 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 that returns index of row
// with maximum number of 1s.
static int rowWithMax1s(int mat[][])
{
// Initialize max values
int max_row_index = 0, max = -1;
// Traverse for each row and count number of 1s
// by finding the index of first 1
int i, index;
for (i = 0; i < R; i++)
{
index = first (mat[i], 0, C-1);
if (index != -1 && C-index > max)
{
max = C - index;
max_row_index = i;
}
}
return max_row_index;
}
// 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}};
System.out.print("Index of row with maximum 1s is " + rowWithMax1s(mat));
}
}
Python3
# Python implementation of the approach
R,C = 4,4
# Function to find the index of first index
# of 1 in a boolean 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 that returns index of row
# with maximum number of 1s.
def rowWithMax1s(mat):
# Initialize max values
max_row_index,Max = 0,-1
# Traverse for each row and count number of 1s
# by finding the index of first 1
for i in range(R):
index = first (mat[i], 0, C-1)
if (index != -1 and C-index > Max):
Max = C - index;
max_row_index = i
return max_row_index
# Driver Code
mat = [[0, 0, 0, 1],
[0, 1, 1, 1],
[1, 1, 1, 1],
[0, 0, 0, 0]]
print("Index of row with maximum 1s is " + str(rowWithMax1s(mat)))
# This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
static int R = 4;
static int C = 4;
// Function to find the index of first index
// of 1 in a bool 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;
}
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;
}
// Function that returns index of row
// with maximum number of 1s.
static int rowWithMax1s(int [,]mat)
{
// Initialize max values
int max_row_index = 0, max = -1;
// Traverse for each row and count number of 1s
// by finding the index of first 1
int i, index;
for (i = 0; i < R; i++) {
int []row = GetRow(mat,i);
index = first(row, 0, C - 1);
if (index != -1 && C - index > max) {
max = C - index;
max_row_index = i;
}
}
return max_row_index;
}
// 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 } };
Console.Write("Index of row with maximum 1s is " + rowWithMax1s(mat));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program for the above approach
var R = 4 ;
var C = 4 ;
// Function to find the index of first index
// of 1 in a boolean 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 that returns index of row
// with maximum number of 1s.
function rowWithMax1s(mat)
{
// Initialize max values
var max_row_index = 0, max = -1;
// Traverse for each row and count number of 1s
// by finding the index of first 1
var i, index;
for (i = 0; i < R; i++)
{
index = first (mat[i], 0, C-1);
if (index != -1 && C-index > max)
{
max = C - index;
max_row_index = i;
}
}
return max_row_index;
}
// Driver Code
var mat = [[0, 0, 0, 1],
[0, 1, 1, 1],
[1, 1, 1, 1],
[0, 0, 0, 0]];
document.write("Index of row with maximum 1s is " + rowWithMax1s(mat));
// This code is contributed by Rajput-Ji
</script>
Producción
Index of row with maximum 1s is 2
Complejidad de tiempo: O(m*n)
Complejidad de espacio: O(1)
Podemos hacerlo mejor. Dado que cada fila está ordenada, podemos usar la búsqueda binaria para contar los 1 en cada fila. Encontramos el índice de primera instancia de 1 en cada fila. El conteo de 1 será igual al número total de columnas menos el índice del primer 1.
Implementación: vea el siguiente código para la implementación del enfoque anterior.
C++
// CPP program to find the row
// with maximum number of 1s
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
// Function to find the index of first instance
// of 1 in a boolean 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 that returns index of row
// with maximum number of 1s.
int rowWithMax1s(bool mat[R][C])
{
// Initialize max values
int max_row_index = 0, max = -1;
// Traverse for each row and count number of 1s
// by finding the index of first 1
int i, index;
for (i = 0; i < R; i++)
{
index = first (mat[i], 0, C-1);
if (index != -1 && C-index > max)
{
max = C - index;
max_row_index = i;
}
}
return max_row_index;
}
// Driver Code
int main()
{
bool mat[R][C] = { {0, 0, 0, 1},
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}};
cout << "Index of row with maximum 1s is " << rowWithMax1s(mat);
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to find the row
// with maximum number of 1s
#include <stdio.h>
#define R 4
#define C 4
// Function to find the index of first index
// of 1 in a boolean 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 that returns index of row
// with maximum number of 1s.
int rowWithMax1s(bool mat[R][C])
{
// Initialize max values
int max_row_index = 0, max = -1;
// Traverse for each row and count number of 1s
// by finding the index of first 1
int i, index;
for (i = 0; i < R; i++)
{
index = first (mat[i], 0, C-1);
if (index != -1 && C-index > max)
{
max = C - index;
max_row_index = i;
}
}
return max_row_index;
}
// Driver Code
int main()
{
bool mat[R][C] = { {0, 0, 0, 1},
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}};
printf("Index of row with maximum 1s is %d "
, rowWithMax1s(mat));
return 0;
}
Java
// Java program to find the row
// with maximum number of 1s
import java.io.*;
class GFG {
static int R = 4, C = 4;
// Function to find the index of first index
// of 1 in a boolean 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 that returns index of row
// with maximum number of 1s.
static int rowWithMax1s(int mat[][])
{
// Initialize max values
int max_row_index = 0, max = -1;
// Traverse for each row and count number of
// 1s by finding the index of first 1
int i, index;
for (i = 0; i < R; i++) {
index = first(mat[i], 0, C - 1);
if (index != -1 && C - index > max) {
max = C - index;
max_row_index = i;
}
}
return max_row_index;
}
// 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 } };
System.out.println("Index of row with maximum 1s is "
+ rowWithMax1s(mat));
}
}
// This code is contributed by 'Gitanjali'.
Python3
# Python3 program to find the row
# with maximum number of 1s
# Function to find the index
# of first index of 1 in a
# boolean 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 that returns
# index of row with maximum
# number of 1s.
def rowWithMax1s( mat):
# Initialize max values
R = len(mat)
C = len(mat[0])
max_row_index = 0
max = -1
# Traverse for each row and
# count number of 1s by finding
# the index of first 1
for i in range(0, R):
index = first (mat[i], 0, C - 1)
if index != -1 and C - index > max:
max = C - index
max_row_index = i
return max_row_index
# Driver Code
mat = [[0, 0, 0, 1],
[0, 1, 1, 1],
[1, 1, 1, 1],
[0, 0, 0, 0]]
print ("Index of row with maximum 1s is",
rowWithMax1s(mat))
# This code is contributed
# by shreyanshi_arun
C#
// C# program to find the row with maximum
// number of 1s
using System;
class GFG
{
public static int R = 4, C = 4;
// Function to find the index of first index
// of 1 in a boolean array arr[]
public 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 that returns index of row
// with maximum number of 1s.
public static int rowWithMax1s(int[][] mat)
{
// Initialize max values
int max_row_index = 0, max = -1;
// Traverse for each row and count number
// of 1s by finding the index of first 1
int i, index;
for (i = 0; i < R; i++)
{
index = first(mat[i], 0, C - 1);
if (index != -1 && C - index > max)
{
max = C - index;
max_row_index = i;
}
}
return max_row_index;
}
// Driver Code
public static void Main(string[] args)
{
int[][] mat = new int[][]
{
new int[] {0, 0, 0, 1},
new int[] {0, 1, 1, 1},
new int[] {1, 1, 1, 1},
new int[] {0, 0, 0, 0}
};
Console.WriteLine("Index of row with maximum 1s is " +
rowWithMax1s(mat));
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to find the row
// with maximum number of 1s
define("R", 4);
define("C", 4);
// Function to find the index of first
// index of 1 in a boolean array arr[]
function first($arr, $low, $high)
{
if($high >= $low)
{
// Get the middle index
$mid = $low + intval(($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 that returns index of row
// with maximum number of 1s.
function rowWithMax1s($mat)
{
// Initialize max values
$max_row_index = 0;
$max = -1;
// Traverse for each row and count number
// of 1s by finding the index of first 1
for ($i = 0; $i < R; $i++)
{
$index = first ($mat[$i], 0, (C - 1));
if ($index != -1 && (C - $index) > $max)
{
$max = C - $index;
$max_row_index = $i;
}
}
return $max_row_index;
}
// Driver Code
$mat = array(array(0, 0, 0, 1),
array(0, 1, 1, 1),
array(1, 1, 1, 1),
array(0, 0, 0, 0));
echo "Index of row with maximum 1s is " .
rowWithMax1s($mat);
// This code is contributed by rathbhupendra
?>
Javascript
<script>
// JavaScript program to find the row
// with maximum number of 1s
R = 4
C = 4
// Function to find the index of first index
// of 1 in a boolean array arr[]
const first = (arr, low, high) => {
if (high >= low) {
// Get the middle index
let 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 that returns index of row
// with maximum number of 1s.
const rowWithMax1s = (mat) => {
// Initialize max values
let max_row_index = 0, max = -1;
// Traverse for each row and count number of 1s
// by finding the index of first 1
let i, index;
for (i = 0; i < R; i++) {
index = first(mat[i], 0, C - 1);
if (index != -1 && C - index > max) {
max = C - index;
max_row_index = i;
}
}
return max_row_index;
}
// Driver Code
let mat = [
[0, 0, 0, 1],
[0, 1, 1, 1],
[1, 1, 1, 1],
[0, 0, 0, 0]
];
document.write(`Index of row with maximum 1s is ${rowWithMax1s(mat)}`);
// This code is contributed by rakeshsahni
</script>
Producción
Index of row with maximum 1s is 2
Complejidad de tiempo: O (mLogn) donde m es el número de filas y n es el número de columnas en la array.
Espacio auxiliar: O (Log n), ya que se crea una pila implícita debido a la recursividad.
La solución anterior se puede optimizar aún más . En lugar de hacer una búsqueda binaria en cada fila, primero verificamos si la fila tiene más 1 que el máximo hasta el momento. Si la fila tiene más 1, solo cuente 1 en la fila. Además, para contar 1 seguidos, no hacemos búsqueda binaria en fila completa, buscamos antes del índice del último máximo.
Implementación: La siguiente es una versión optimizada de la solución anterior.
C++
#include <bits/stdc++.h>
using namespace std;
// The main function that returns index
// of row with maximum number of 1s.
int rowWithMax1s(bool mat[R][C])
{
int i, index;
// Initialize max using values from first row.
int max_row_index = 0;
int max = first(mat[0], 0, C - 1);
// Traverse for each row and count number of 1s
// by finding the index of first 1
for (i = 1; i < R; i++)
{
// Count 1s in this row only if this row
// has more 1s than max so far
// Count 1s in this row only if this row
// has more 1s than max so far
if (max != -1 && mat[i][C - max - 1] == 1)
{
// Note the optimization here also
index = first (mat[i], 0, C - max);
if (index != -1 && C - index > max)
{
max = C - index;
max_row_index = i;
}
}
else
{
max = first(mat[i], 0, C - 1);
}
}
return max_row_index;
}
// This code is contributed by rathbhupendra
C
// The main function that returns index of row with maximum number of 1s.
int rowWithMax1s(bool mat[R][C])
{
int i, index;
// Initialize max using values from first row.
int max_row_index = 0;
int max = first(mat[0], 0, C-1);
// Traverse for each row and count number of 1s by finding the index
// of first 1
for (i = 1; i < R; i++)
{
// Count 1s in this row only if this row has more 1s than
// max so far
// Count 1s in this row only if this row has more 1s than
// max so far
if (max != -1 && mat[i][C-max-1] == 1)
{
// Note the optimization here also
index = first (mat[i], 0, C-max);
if (index != -1 && C-index > max)
{
max = C - index;
max_row_index = i;
}
}
else {
max = first(mat[i], 0, C - 1);
}
}
return max_row_index;
}
Java
public class gfg
{
// The main function that returns index
// of row with maximum number of 1s.
static int rowWithMax1s(boolean mat[][])
{
int i, index;
// Initialize max using values from first row.
int max_row_index = 0;
int max = first(mat[0], 0, C - 1);
// Traverse for each row and count number of 1s
// by finding the index of first 1
for (i = 1; i < R; i++)
{
// Count 1s in this row only if this row
// has more 1s than max so far
// Count 1s in this row only if this row
// has more 1s than max so far
if (max != -1 && mat[i][C - max - 1] == 1)
{
// Note the optimization here also
index = first (mat[i], 0, C - max);
if (index != -1 && C - index > max)
{
max = C - index;
max_row_index = i;
}
}
else
{
max = first(mat[i], 0, C - 1);
}
}
return max_row_index;
}
}
// This code is contributed by divyesh072019.
Python3
# The main function that returns index # of row with maximum number of 1s. def rowWithMax1s(mat) : # Initialize max using values from first row. max_row_index = 0; max = first(mat[0], 0, C - 1) # Traverse for each row and count number of 1s # by finding the index of first 1 for i in range(1, R): # Count 1s in this row only if this row # has more 1s than max so far # Count 1s in this row only if this row # has more 1s than max so far if (max != -1 and mat[i][C - max - 1] == 1): # Note the optimization here also index = first (mat[i], 0, C - max) if (index != -1 and C - index > max): max = C - index max_row_index = i else: max = first(mat[i], 0, C - 1) return max_row_index; # This code is contributed by Dharanendra L V
C#
using System;
class GFG
{
// The main function that returns index
// of row with maximum number of 1s.
static int rowWithMax1s(bool[,] mat)
{
int i, index;
// Initialize max using values from first row.
int max_row_index = 0;
int max = first(mat[0], 0, C - 1);
// Traverse for each row and count number of 1s
// by finding the index of first 1
for (i = 1; i < R; i++)
{
// Count 1s in this row only if this row
// has more 1s than max so far
// Count 1s in this row only if this row
// has more 1s than max so far
if (max != -1 && mat[i,C - max - 1] == 1)
{
// Note the optimization here also
index = first (mat[i], 0, C - max);
if (index != -1 && C - index > max)
{
max = C - index;
max_row_index = i;
}
}
else
{
max = first(mat[i], 0, C - 1);
}
}
return max_row_index;
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// The main function that returns index
// of row with maximum number of 1s.
function rowWithMax1s(mat)
{
let i, index;
// Initialize max using values from first row.
let max_row_index = 0;
let max = first(mat[0], 0, C - 1);
// Traverse for each row and count number of 1s
// by finding the index of first 1
for(i = 1; i < R; i++)
{
// Count 1s in this row only if this row
// has more 1s than max so far
// Count 1s in this row only if this row
// has more 1s than max so far
if (max != -1 && mat[i][C - max - 1] == 1)
{
// Note the optimization here also
index = first (mat[i], 0, C - max);
if (index != -1 && C - index > max)
{
max = C - index;
max_row_index = i;
}
}
else
{
max = first(mat[i], 0, C - 1);
}
}
return max_row_index;
}
// This code is contributed by suresh07
</script>
La complejidad de tiempo en el peor de los casos de la versión optimizada anterior también es O (mLogn), la solución funcionará mejor en promedio.
Gracias a Naveen Kumar Singh por sugerir la solución anterior.
El peor caso de la solución anterior ocurre para una array como la siguiente.
0 0 0 … 0 1
0 0 0 ..0 1 1
0 … 0 1 1 1
….0 1 1 1 1El siguiente método funciona en la complejidad de tiempo O (m + n) en el peor de los casos .
- Paso 1: obtenga el índice del primer (o más a la izquierda) 1 en la primera fila.
- Paso 2: haga lo siguiente para cada fila después de la primera fila
- …SI el elemento a la izquierda del anterior 1 más a la izquierda es 0, ignore esta fila.
- …ELSE Mover a la izquierda hasta encontrar un 0. Actualice el índice más a la izquierda a este índice y max_row_index para que sea la fila actual.
- La complejidad del tiempo es O(m+n) porque posiblemente podamos ir tan a la izquierda como avanzamos en el primer paso.
Implementación: A continuación se muestra la implementación de este método.
C++
// C++ program to find the row with maximum
// number of 1s
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
// The main function that returns index of row with maximum
// number of 1s.
int rowWithMax1s(bool mat[R][C])
{
// Initialize first row as row with max 1s
int j,max_row_index = 0;
j = C - 1;
for (int i = 0; i < R; i++) {
// Move left until a 0 is found
bool flag=false; //to check whether a row has more 1's than previous
while (j >= 0 && mat[i][j] == 1) {
j = j - 1; // Update the index of leftmost 1
// seen so far
flag=true ;//present row has more 1's than previous
}
// if the present row has more 1's than previous
if(flag){
max_row_index = i; // Update max_row_index
}
}
if(max_row_index==0&&mat[0][C-1]==0)
return -1;
return max_row_index;
}
// Driver Code
int main()
{
bool mat[R][C] = { {0, 0, 0, 1},
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}};
cout << "Index of row with maximum 1s is " << rowWithMax1s(mat);
return 0;
}
// this code is contributed by Rishabh Chauhan
Java
// Java program to find the row
// with maximum number of 1s
import java.io.*;
class GFG {
static int R = 4, C = 4;
// Function that returns index of row
// with maximum number of 1s.
static int rowWithMax1s(int mat[][])
{
// Initialize first row as row with max 1s
int j,max_row_index = 0;
j = C - 1;
for (int i = 0; i < R; i++) {
// Move left until a 0 is found
while (j >= 0 && mat[i][j] == 1) {
j = j - 1; // Update the index of leftmost 1
// seen so far
max_row_index = i; // Update max_row_index
}
}
if(max_row_index==0&&mat[0][C-1]==0)
return -1;
return max_row_index;
}
// 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 } };
System.out.println("Index of row with maximum 1s is "+ rowWithMax1s(mat));
}
}
// This code is contributed by 'Rishabh Chauhan'.
Python3
# Python3 program to find the row
# with maximum number of 1s
# Function that returns
# index of row with maximum
# number of 1s.
def rowWithMax1s( mat):
# Initialize max values
R = len(mat)
C = len(mat[0])
max_row_index = 0
index=C-1;
# Traverse for each row and
# count number of 1s by finding
# the index of first 1
for i in range(0, R):
flag=False #to check whether a row has more 1's than previous
while(index >=0 and mat[i][index]==1):
flag=True #present row has more 1's than previous
index-=1
if(flag): #if the present row has more 1's than previous
max_row_index = i
if max_row_index==0 and mat[0][C-1]==0:
return 0;
return max_row_index
# Driver Code
mat = [[0, 0, 0, 1],
[0, 1, 1, 1],
[1, 1, 1, 1],
[0, 0, 0, 0]]
print ("Index of row with maximum 1s is",
rowWithMax1s(mat))
# This code is contributed
# by Rishabh Chauhan
C#
// C# program to find the row with maximum
// number of 1s
using System;
class GFG
{
public static int R = 4, C = 4;
// Function that returns index of row
// with maximum number of 1s.
public static int rowWithMax1s(int[][] mat)
{
// Initialize max values
int max_row_index = 0;
int i, index;
index=C-1;
for (i = 0; i < R; i++)
{
if (index >=0 && mat[i][index]==1)
{
index-=1;
max_row_index = i;
}
}
if (max_row_index==0&&mat[0][C-1]==0)
return 0;
return max_row_index;
}
// Driver Code
public static void Main(string[] args)
{
int[][] mat = new int[][]
{
new int[] {0, 0, 0, 1},
new int[] {0, 1, 1, 1},
new int[] {1, 1, 1, 1},
new int[] {0, 0, 0, 0}
};
Console.WriteLine("Index of row with maximum 1s is " +rowWithMax1s(mat));
}
}
// This code is contributed by Rishabh Chauhan
Javascript
<script>
// JavaScript program for the above approach
let R = 4
let C = 4
// The main function that returns index of row with maximum
// number of 1s.
function rowWithMax1s(mat)
{
// Initialize first row as row with max 1s
let j, max_row_index = 0;
j = C - 1;
for (let i = 0; i < R; i++)
{
// Move left until a 0 is found
let flag = false;
// to check whether a row has more 1's than previous
while (j >= 0 && mat[i][j] == 1)
{
j = j - 1; // Update the index of leftmost 1
// seen so far
flag = true;//present row has more 1's than previous
}
// if the present row has more 1's than previous
if (flag)
{
max_row_index = i; // Update max_row_index
}
}
if (max_row_index == 0 && mat[0][C - 1] == 0)
return -1;
return max_row_index;
}
// Driver Code
let mat = [[0, 0, 0, 1],
[0, 1, 1, 1],
[1, 1, 1, 1],
[0, 0, 0, 0]];
document.write("Index of row with maximum 1s is " + rowWithMax1s(mat));
// This code is contributed by Potta Lokesh
</script>
Producción
Index of row with maximum 1s is 2
Complejidad de tiempo: O(m+n) donde m es el número de filas yn es el número de columnas en la array.
Espacio auxiliar: O(1), ya que se crea una pila implícita debido a la recursividad.
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