Рубрики

Найти строку с максимальным количеством 1 с

Массивы, Матрицы, Поиск

Дан логический 2D-массив, в котором отсортирована каждая строка. Найдите строку с максимальным количеством 1 с.
Пример:

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

Простой метод состоит в том, чтобы выполнить пошаговый обход матрицы, посчитать количество единиц в каждой строке и сравнить число с макс. Наконец, верните индекс строки с максимумом 1 с. Временная сложность этого метода составляет O (m * n), где m — количество строк, а n — количество столбцов в матрице.

Мы можем сделать лучше. Поскольку каждая строка отсортирована, мы можем использовать двоичный поиск для подсчета 1 с в каждой строке. Мы находим индекс первого экземпляра 1 в каждой строке. Количество 1 с будет равно общему количеству столбцов минус индекс первого 1.

См. Следующий код для реализации вышеупомянутого подхода.

C ++

// Программа CPP для поиска строки
// с максимальным количеством 1 с
#include <bits/stdc++.h>

using namespace std;

#define R 4 
#define C 4 

  
// Функция для поиска индекса первого индекса
// из 1 в логическом массиве arr []

int first(bool arr[], int low, int high) 

{ 

    if(high >= low) 

    { 

        // Получить средний индекс

        int mid = low + (high - low)/2; 

      

        // Проверяем, является ли элемент по среднему индексу первым 1

        if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) 

            return mid; 

      

        // Если элемент равен 0, повторить для правой стороны

        else if (arr[mid] == 0) 

            return first(arr, (mid + 1), high); 

          

        // Если элемент не первый 1, повторить для левой стороны

        else

            return first(arr, low, (mid -1)); 

    } 

    return -1; 

} 

  
// Функция, которая возвращает индекс строки
// с максимальным количеством 1 с.

int rowWithMax1s(bool mat[R][C]) 

{ 

    // Инициализируем максимальные значения

    int max_row_index = 0, max = -1; 

  

    // Пройдемся по каждой строке и посчитаем число 1

    // найдем индекс первого 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; 

} 

  
// Код драйвера

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; 

} 

  
// Это код, предоставленный rathbhupendra

С

// C программа для поиска строки
// с максимальным количеством 1 с
#include <stdio.h>
#define R 4
#define C 4

  
// Функция для поиска индекса первого индекса
// из 1 в логическом массиве arr []

int first(bool arr[], int low, int high)

{

if(high >= low)

{

    // Получить средний индекс

    int mid = low + (high - low)/2; 

  

    // Проверяем, является ли элемент по среднему индексу первым 1

    if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)

    return mid;

  

    // Если элемент равен 0, повторить для правой стороны

    else if (arr[mid] == 0)

    return first(arr, (mid + 1), high);

      

    // Если элемент не первый 1, повторить для левой стороны

    else 

    return first(arr, low, (mid -1));

}

return -1;

}

  
// Функция, которая возвращает индекс строки
// с максимальным количеством 1 с.

int rowWithMax1s(bool mat[R][C])

{

    // Инициализируем максимальные значения

    int max_row_index = 0, max = -1; 

  

    // Пройдемся по каждой строке и посчитаем число 1

    // найдем индекс первого 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;

}

  
// Код драйвера

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-программа для поиска строки
// с максимальным количеством 1 с

import java.io.*;

  

class GFG {

    static int R = 4, C = 4;

    // Функция для поиска индекса первого индекса

    // из 1 в логическом массиве arr []

    static int first(int arr[], int low, int high)

    {

        if (high >= low) {

            // Получить средний индекс

            int mid = low + (high - low) / 2;

  

            // Проверяем, является ли элемент по среднему индексу первым 1

            if ((mid == 0 || (arr[mid - 1] == 0)) && arr[mid] == 1)

                return mid;

  

            // Если элемент равен 0, повторить для правой стороны

            else if (arr[mid] == 0)

                return first(arr, (mid + 1), high);

                  

            // Если элемент не первый 1, повторить для левой стороны

            else 

                return first(arr, low, (mid - 1));

        }

        return -1;

    }

  

    // Функция, которая возвращает индекс строки

    // с максимальным количеством 1 с.

    static int rowWithMax1s(int mat[][])

    {

        // Инициализируем максимальные значения

        int max_row_index = 0, max = -1; 

  

        // Пройдемся по каждой строке и посчитаем количество

        // 1s путем нахождения индекса первого 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;

    }

    // Код драйвера

    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));

    }

}

  
// Этот код предоставлен Gitanjali.

Python 3

# Python3 программа для поиска строки
# с максимальным количеством 1 с

  
# Функция для поиска индекса
№ первого индекса 1 в
# логический массив arr []

def first( arr, low, high):

    if high >= low:

          

        # Получить средний индекс

        mid = low + (high - low)//2

  

        # Проверьте, если элемент в

        # средний индекс первый 1

        if (mid == 0 or arr[mid - 1] == 0) and arr[mid] == 1:

            return mid

  

        # Если элемент равен 0,

        # повторить для правой стороны

        elif arr[mid] == 0:

            return first(arr, (mid + 1), high)

      

        # Если элемент не первый 1,

        # повторить для левой стороны

        else:

            return first(arr, low, (mid - 1))

    return -1

  
# Функция, которая возвращает
# индекс строки с максимумом
# число 1 с.

def rowWithMax1s( mat):

      

    # Инициализировать максимальные значения

    R = len(mat)

    C = len(mat[0])

    max_row_index = 0

    max = -1

      

    # Траверс для каждой строки и

    # посчитать количество 1 с, найдя

    # индекс первого 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

  
Код водителя

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))

  
# Этот код добавлен
# by shreyanshi_arun

C #

// C # программа для поиска строки с максимумом
// количество единиц

using System;

  

class GFG

{

public static int R = 4, C = 4;

  
// Функция для поиска индекса первого индекса
// из 1 в логическом массиве arr []

public static int first(int[] arr, 

                        int low, int high)

{

    if (high >= low)

    {

        // Получить средний индекс

        int mid = low + (high - low) / 2;

  

        // Проверяем, находится ли элемент посередине

        // индекс первый 1

        if ((mid == 0 || (arr[mid - 1] == 0)) &&

                          arr[mid] == 1)

        {

            return mid;

        }

  

        // Если элемент равен 0, повторить

        // для правой стороны

        else if (arr[mid] == 0)

        {

            return first(arr, (mid + 1), high);

        }

  

        // Если элемент не первый 1, повторить

        // для левой стороны

        else

        {

            return first(arr, low, (mid - 1));

        }

    }

    return -1;

}

  
// Функция, которая возвращает индекс строки
// с максимальным количеством 1 с.

public static int rowWithMax1s(int[][] mat)

{

    // Инициализируем максимальные значения

    int max_row_index = 0, max = -1;

  

    // Траверс для каждой строки и числа

    // из 1, найдя индекс первого 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;

}

  
// Код драйвера

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));

}
}

  
// Этот код предоставлен Shrikant13

PHP

<?php
// PHP программа для поиска строки
// с максимальным количеством 1 с

define("R", 4);

define("C", 4); 

  
// Функция для поиска индекса первого
// индекс 1 в логическом массиве arr []

function first($arr, $low, $high) 

{ 

    if($high >= $low) 

    { 

        // Получить средний индекс

        $mid = $low + intval(($high - $low) / 2); 

      

        // Проверяем, находится ли элемент посередине

        // индекс первый 1

        if (($mid == 0 || $arr[$mid - 1] == 0) && 

                          $arr[$mid] == 1) 

        return $mid; 

      

        // Если элемент равен 0, повторить для

        // правая сторона

        else if ($arr[$mid] == 0) 

        return first($arr, ($mid + 1), $high); 

          

        // Если элемент не первый 1, повторить

        // для левой стороны

        else

        return first($arr, $low, ($mid - 1)); 

    } 

    return -1; 

} 

  
// Функция, которая возвращает индекс строки
// с максимальным количеством 1 с.

function rowWithMax1s($mat) 

{ 

      

    // Инициализируем максимальные значения

    $max_row_index = 0;

    $max = -1; 

  

    // Траверс для каждой строки и числа

    // из 1, найдя индекс первого 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; 

} 

  
// Код драйвера

$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); 

  
// Этот код предоставлен rathbhupendra
?>


Выход:

Index of row with maximum 1s is 2

Сложность времени: O (mLogn), где m — количество строк, а n — количество столбцов в матрице.

Вышеуказанное решение может быть дополнительно оптимизировано . Вместо того, чтобы выполнять бинарный поиск в каждой строке, мы сначала проверяем, имеет ли строка больше 1 с, чем макс. Если в строке больше 1, то считайте только 1 в строке. Кроме того, чтобы посчитать 1 с в строке, мы не выполняем бинарный поиск в полной строке, мы выполняем поиск до индекса последнего максимума.

Ниже приведена оптимизированная версия вышеуказанного решения.

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Основная функция, которая возвращает индекс
// строки с максимальным количеством 1 с.

int rowWithMax1s(bool mat[R][C]) 

{ 

    int i, index; 

  

    // Инициализируем max используя значения из первой строки.

    int max_row_index = 0; 

    int max = first(mat[0], 0, C - 1); 

  

    // Пройдемся по каждой строке и посчитаем число 1

    // найдем индекс первого 1

    for (i = 1; i < R; i++) 

    { 

        // Считаем 1 в этой строке, только если эта строка

        // имеет больше 1 с макс

  

        // Считаем 1 в этой строке, только если эта строка

        // имеет больше 1 с макс

        if (max != -1 && mat[i][C - max - 1] == 1) 

        { 

            // Обратите внимание на оптимизацию здесь

            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; 

} 

  
// Этот код предоставлен rathbhupendra

С

// Основная функция, которая возвращает индекс строки с максимальным числом 1 с.

int rowWithMax1s(bool mat[R][C])

{

    int i, index;

   

    // Инициализируем max используя значения из первой строки.

    int max_row_index = 0;

    int max = first(mat[0], 0, C-1);

   

    // Пройдемся по каждой строке и посчитаем число 1, найдя индекс

    // первого 1

    for (i = 1; i < R; i++)

    {

        // Считаем 1 в этой строке, только если в этой строке больше 1

        // макс

  

        // Считаем 1 в этой строке, только если в этой строке больше 1

        // макс

        if (max != -1 && mat[i][C-max-1] == 1)

        {

            // Обратите внимание на оптимизацию здесь

            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;

}


Наихудшая временная сложность оптимизированной версии выше также равна O (mLogn), решение в среднем будет работать лучше. Спасибо Навину Кумар Сингху за предложенное выше решение.

Наихудший случай вышеуказанного решения имеет место для матрицы, подобной следующей.
0 0 0… 0 1
0 0 0 ..0 1 1
0… 0 1 1 1
… .0 1 1 1 1

Следующий метод работает в O (m + n) временной сложности в худшем случае .

Шаг 1: Получить индекс первой (или самой левой) 1 в первом ряду.

Шаг 2: Делайте следующее для каждого ряда после первого ряда
… Если элемент слева от предыдущего левого 1 равен 0, игнорировать эту строку.
… В противном случае двигаться влево, пока не будет найден 0. Обновите крайний левый индекс до этого индекса, а max_row_index будет текущей строкой.

Сложность по времени составляет O (m + n), потому что мы, возможно, можем пойти так далеко налево, как мы продвинулись на первом шаге.

Ниже приведена реализация этого метода на C ++.

// Основная функция, которая возвращает индекс строки с максимальным числом 1 с.

int rowWithMax1s(bool mat[R][C])

{

    // Инициализируем первую строку как строку с максимумом 1 с

    int max_row_index = 0;

  

    // Функция first () возвращает индекс первой 1 в строке 0.

    // Используем этот индекс для инициализации индекса самой левой 1, видимой до сих пор

    int j = first(mat[0], 0, C-1);

    if (j == -1) // если 1 отсутствует в первой строке

      j = C - 1;

  

    for (int i = 1; i < R; i++)

    {

        // Двигаться влево, пока не будет найден 0

        while (j >= 0 && mat[i][j] == 1)

        {

           j = j-1;  // Обновляем индекс самой левой 1, замеченной до сих пор

           max_row_index = i;  // Обновляем max_row_index

        }

    }

    return max_row_index;

}

Спасибо Tylor, Ankan и Palash за их вклад.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти строку с максимальным количеством 1 с

0.00 (0%) 0 votes