Encuentre la fila con el número máximo de 1

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 1

El 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *