Рубрики

Подсчет отрицательных чисел в матрице по столбцам и по строкам

Найдите количество отрицательных чисел в отсортированной по столбцам / по строкам матрице M [] []. Предположим, что M имеет n строк и m столбцов.

Пример:

Input:  M =  [-3, -2, -1,  1]
             [-2,  2,  3,  4]
             [4,   5,  7,  8]
Output : 4
We have 4 negative numbers in this matrix

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Наивное решение
Вот наивное, неоптимальное решение.

Мы начинаем с верхнего левого угла и подсчитываем количество отрицательных чисел по одному, слева направо и сверху вниз.

С приведенным примером:

[-3, -2, -1,  1]
[-2,  2,  3,  4]
[4,   5,  7,  8]

Evaluation process

[?,  ?,  ?,  1]
[?,  2,  3,  4]
[4,  5,  7,  8]

Ниже приведена реализация вышеуказанной идеи.

C ++

// CPP реализация Наивного метода
// для подсчета отрицательных чисел в
// M [n] [m]
#include <bits/stdc++.h>

using namespace std;

  

int countNegative(int M[][4], int n, int m)

{

    int count = 0;

  

    // Следуйте пути, указанному с помощью

    // стрелки выше

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            if (M[i][j] < 0)

                count += 1;

  

            // больше нет отрицательных чисел

            // в этой строке

            else

                break;

        }

    }

    return count;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int M[3][4] = { { -3, -2, -1, 1 },

                    { -2, 2, 3, 4 },

                    { 4, 5, 7, 8 } };

  

    cout << countNegative(M, 3, 4);

    return 0;

}
// Этот код предоставлен Нитешем Кумаром

Джава

// Java-реализация метода Naive
// для подсчета отрицательных чисел в
// M [n] [m]

import java.util.*;

import java.lang.*;

import java.io.*;

  

class GFG {

    static int countNegative(int M[][], int n,

                             int m)

    {

        int count = 0;

  

        // Следуйте пути, указанному с помощью

        // стрелки выше

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) {

                if (M[i][j] < 0)

                    count += 1;

  

                // больше нет отрицательных чисел

                // в этой строке

                else

                    break;

            }

        }

        return count;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        int M[][] = { { -3, -2, -1, 1 },

                      { -2, 2, 3, 4 },

                      { 4, 5, 7, 8 } };

  

        System.out.println(countNegative(M, 3, 4));

    }

}
// Этот код предоставлен Чхави

питон

# Python реализация метода Naive для подсчета
# отрицательных чисел в M [n] [m]

  

def countNegative(M, n, m):

    count = 0

  

    # Следуйте пути, указанному стрелками выше

    for i in range(n):

        for j in range(m): 

  

            if M[i][j] < 0:

                count += 1

  

            else:

                # больше нет отрицательных чисел в этой строке

                break

    return count

  

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

M =

      [-3, -2, -11],

      [-2234],

      [ 4578]

    ]

print(countNegative(M, 3, 4))

C #

// C # реализация Наивного метода
// для подсчета отрицательных чисел в
// M [n] [m]

using System;

  

class GFG {

  

    // Функция для подсчета

    // отрицательное число

    static int countNegative(int[, ] M, int n,

                             int m)

    {

        int count = 0;

  

        // Следуйте указанному пути

        // используя стрелки выше

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) {

                if (M[i, j] < 0)

                    count += 1;

  

                // больше нет отрицательных чисел

                // в этой строке

                else

                    break;

            }

        }

        return count;

    }

  

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

    public static void Main()

    {

        int[, ] M = { { -3, -2, -1, 1 },

                      { -2, 2, 3, 4 },

                      { 4, 5, 7, 8 } };

  

        Console.WriteLine(countNegative(M, 3, 4));

    }

}

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

PHP

<?php
// PHP реализация метода Naive
// для подсчета отрицательных чисел в
// M [n] [m]

  

function countNegative($M, $n, $m)

{

    $count = 0;

  

    // Следуйте пути, указанному с помощью

    // стрелки выше

    for( $i = 0; $i < $n; $i++)

    {

        for( $j = 0; $j < $m; $j++)

        {

            if( $M[$i][$j] < 0 )

                $count += 1;

          

            // больше нет отрицательных чисел

            // в этой строке

            else

                break;

        }

    }

    return $count;

}

  

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

    $M = array(array(-3, -2, -1, 1),

               array(-2, 2, 3, 4),

               array(4, 5, 7, 8));

      

    echo countNegative($M, 3, 4);

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

Выход :

4

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

Оптимальным решением

Вот более эффективное решение:

  1. Мы начинаем с правого верхнего угла и находим позицию последнего отрицательного числа в первом ряду.
  2. Используя эту информацию, мы находим позицию последнего отрицательного числа во втором ряду.
  3. Мы продолжаем повторять этот процесс до тех пор, пока у нас не закончатся отрицательные числа или мы не доберемся до последнего ряда.
With the given example:
[-3, -2, -1,  1]
[-2,  2,  3,  4]
[4,   5,  7,  8]

Here's the idea:
[-3, -2,  ?,  ?] -> Found 3 negative numbers in this row
[ ?,  ?,  ?,  4] -> Found 1 negative number in this row
[ ?,  5,  7,  8] -> No negative numbers in this row 

C ++

// CPP реализация Efficient
// метод подсчета отрицательных чисел
// в М [п] [м]
#include <bits/stdc++.h>

using namespace std;

  

int countNegative(int M[][4], int n, int m)

{

    // инициализировать результат

    int count = 0;

  

    // Начинаем с верхнего правого угла

    int i = 0;

    int j = m - 1;

  

    // Следуйте пути, указанному с помощью

    // стрелки выше

    while (j >= 0 && i < n) {

        if (M[i][j] < 0) {

            // j - индекс

            // последнее отрицательное число

            // в этом ряду. Здесь

            // должно быть (j + 1)

            count += j + 1;

  

            // отрицательные числа в

            // этот ряд

            i += 1;

        }

  

        // двигаемся влево и видим

        // если мы можем найти отрицательный

        // номер там

        else

            j -= 1;

    }

  

    return count;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int M[3][4] = { { -3, -2, -1, 1 },

                    { -2, 2, 3, 4 },

                    { 4, 5, 7, 8 } };

  

    cout << countNegative(M, 3, 4);

  

    return 0;

}
// Этот код предоставлен Нитешем Кумаром

Джава

// Java-реализация Efficient
// метод подсчета отрицательных чисел
// в М [п] [м]

import java.util.*;

import java.lang.*;

import java.io.*;

  

class GFG {

    static int countNegative(int M[][], int n,

                             int m)

    {

        // инициализировать результат

        int count = 0;

  

        // Начинаем с верхнего правого угла

        int i = 0;

        int j = m - 1;

  

        // Следуйте пути, указанному с помощью

        // стрелки выше

        while (j >= 0 && i < n) {

            if (M[i][j] < 0) {

                // j - индекс

                // последнее отрицательное число

                // в этом ряду. Здесь

                // должно быть (j + 1)

                count += j + 1;

  

                // отрицательные числа в

                // этот ряд

                i += 1;

            }

  

            // двигаемся влево и видим

            // если мы можем найти отрицательный

            // номер там

            else

                j -= 1;

        }

        return count;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        int M[][] = { { -3, -2, -1, 1 },

                      { -2, 2, 3, 4 },

                      { 4, 5, 7, 8 } };

  

        System.out.println(countNegative(M, 3, 4));

    }

}
// Этот код предоставлен Чхави

питон

# Реализация Python эффективного метода для подсчета
# отрицательных чисел в M [n] [m]

  

def countNegative(M, n, m):

  

    count = 0 # инициализировать результат

  

    # Начните с верхнего правого угла

    i = 0 

    j = m - 1  

  

    # Следуйте пути, указанному стрелками выше

    while j >= 0 and i < n:

  

        if M[i][j] < 0:

  

            # j - индекс последнего отрицательного числа

            # в этом ряду. Так что должно быть (J + 1)

            count += (j + 1

  

            # отрицательные числа в этом ряду.

            i += 1

  

        else:

            # переместимся влево и посмотрим, сможем ли мы

            # найти отрицательное число там

             j -= 1

    return count

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

M =

      [-3, -2, -11],

      [-2234],

      [4,   578]

    ]

print(countNegative(M, 3, 4))

C #

// C # реализация Efficient
// метод подсчета негатива
// числа в M [n] [m]

using System;

  

class GFG {

  

    // Функция для подсчета

    // отрицательное число

    static int countNegative(int[, ] M, int n,

                             int m)

    {

  

        // инициализировать результат

        int count = 0;

  

        // Начинаем с верхнего правого угла

        int i = 0;

        int j = m - 1;

  

        // Следуйте указанному пути

        // используя стрелки выше

        while (j >= 0 && i < n) {

            if (M[i, j] < 0) {

                // j - индекс

                // последнее отрицательное число

                // в этом ряду. Здесь

                // должно быть (j + 1)

                count += j + 1;

  

                // отрицательные числа в

                // этот ряд

                i += 1;

            }

  

            // двигаемся влево и видим

            // если мы можем найти отрицательный

            // номер там

            else

                j -= 1;

        }

        return count;

    }

  

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

    public static void Main()

    {

        int[, ] M = { { -3, -2, -1, 1 },

                      { -2, 2, 3, 4 },

                      { 4, 5, 7, 8 } };

  

        Console.WriteLine(countNegative(M, 3, 4));

    }

}

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

PHP

<?php
// Реализация PHP эффективной
// метод подсчета отрицательных чисел
// в М [п] [м]

  

function countNegative( $M, $n, $m)

{

      

    // инициализировать результат

    $count = 0; 

  

    // Начинаем с верхнего правого угла

    $i = 0;

    $j = $m - 1; 

  

    // Следуйте пути, указанному с помощью

    // стрелки выше

    while( $j >= 0 and $i < $n )

    {

        if( $M[$i][$j] < 0 )

        {

            // j - индекс

            // последнее отрицательное число

            // в этом ряду. Здесь

            // должно быть (j + 1)

            $count += $j + 1;

  

            // отрицательные числа в

            // этот ряд

            $i += 1;

        }

              

        // двигаемся влево и видим

        // если мы можем найти отрицательный

        // номер там

        else

        $j -= 1;

    }

  

    return $count;

}

  

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

    $M = array(array(-3, -2, -1, 1),

               array(-2, 2, 3, 4),

               array(4, 5, 7, 8));

      

    echo countNegative($M, 3, 4);

      

    return 0; 

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

Выход :

4

С помощью этого решения мы можем теперь решить эту проблему за O (n + m) время.

Более оптимальное решение

Вот более эффективное решение, использующее бинарный поиск вместо линейного поиска:

  1. Мы начинаем с первой строки и находим позицию последнего отрицательного числа в первой строке, используя бинарный поиск.
  2. Используя эту информацию, мы находим позицию последнего отрицательного числа во второй строке, выполняя бинарный поиск только до позиции последнего отрицательного числа в строке выше.
  3. Мы продолжаем повторять этот процесс до тех пор, пока у нас не закончатся отрицательные числа или мы не доберемся до последнего ряда.
With the given example:
[-3, -2, -1,  1]
[-2,  2,  3,  4]
[4,   5,  7,  8]

Here's the idea:
1. Count is initialized to 0
2. Binary search on full 1st row returns 2 as the index of last negative integer, and we increase count to 0+(2+1) = 3.
3. For 2nd row, we run binary search from index 0 to index 2 and it returns 0 as the index of last negative integer. We increase the count to 3+(0+1) = 4;
4. For 3rd row, first element is > 0, so we end the loop here.

Джава

// Реализация Java более эффективной
// метод подсчета количества отрицательных чисел
// в отсортированной по столбцу матрице M [n] [m]

import java.util.*;

import java.lang.*;

import java.io.*;

  

class GFG {

  

    // Рекурсивный бинарный поиск для получения последнего негатива

    // значение в строке между началом и концом

    static int getLastNegativeIndex(int array[], int start, int end)

    {

        // Базовый вариант

        if (start == end) {

            return start;

        }

  

        // Получить середину для бинарного поиска

        int mid = start + (end - start) / 2;

  

        // Если текущий элемент отрицателен

        if (array[mid] < 0) {

  

            // Если это самый правый минус

            // элемент в текущей строке

            if (mid + 1 < array.length && array[mid + 1] >= 0) {

                return mid;

            }

  

            // Проверка в правой половине массива

            return getLastNegativeIndex(array, mid + 1, end);

        }

        else {

  

            // Проверка в левой половине массива

            return getLastNegativeIndex(array, start, mid - 1);

        }

    }

  

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

    // отрицательные числа в данной матрице

    static int countNegative(int M[][], int n, int m)

    {

  

        // Инициализировать результат

        int count = 0;

  

        // Для сохранения индекса самого правого отрицательного

        // элемент в рассматриваемой строке

        int nextEnd = m - 1;

  

        // перебираем все строки матрицы

        for (int i = 0; i < n; i++) {

  

            // Если первый элемент текущей строки

            // положительно, тогда не будет негативов

            // в матрице ниже или после нее

            if (M[i][0] >= 0) {

                break;

            }

  

            // Запускаем бинарный поиск только до последнего индекса

            // отрицательное целое число в приведенной выше строке

            nextEnd = getLastNegativeIndex(M[i], 0, nextEnd);

            count += nextEnd + 1;

        }

        return count;

    }

  

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

    public static void main(String[] args)

    {

        int M[][] = { { -3, -2, -1, 1 },

                      { -2, 2, 3, 4 },

                      { 4, 5, 7, 8 } };

        int r = M.length;

        int c = M[0].length;

        System.out.println(countNegative(M, r, c));

    }

}
// Этот код предоставлен Rahul Jain

C #

// C # реализация более эффективной
// метод подсчета количества отрицательных чисел
// в отсортированной по столбцу матрице M [n, m]

using System;

using System.Collections.Generic;

  

class GFG 

{

  

    // Рекурсивный бинарный поиск для получения последнего негатива

    // значение в строке между началом и концом

    static int getLastNegativeIndex(int []array, int start, int end)

    {

        // Базовый вариант

        if (start == end) 

        {

            return start;

        }

  

        // Получить середину для бинарного поиска

        int mid = start + (end - start) / 2;

  

        // Если текущий элемент отрицателен

        if (array[mid] < 0) 

        {

  

            // Если это самый правый минус

            // элемент в текущей строке

            if (mid + 1 < array.GetLength(0) && array[mid + 1] >= 0) 

            {

                return mid;

            }

  

            // Проверка в правой половине массива

            return getLastNegativeIndex(array, mid + 1, end);

        }

        else 

        {

  

            // Проверка в левой половине массива

            return getLastNegativeIndex(array, start, mid - 1);

        }

    }

  

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

    // отрицательные числа в данной матрице

    static int countNegative(int [,]M, int n, int m)

    {

  

        // Инициализировать результат

        int count = 0;

  

        // Для сохранения индекса самого правого отрицательного

        // элемент в рассматриваемой строке

        int nextEnd = m - 1;

  

        // перебираем все строки матрицы

        for (int i = 0; i < n; i++) 

        {

  

            // Если первый элемент текущей строки

            // положительно, тогда не будет негативов

            // в матрице ниже или после нее

            if (M[i, 0] >= 0)

            {

                break;

            }

  

            // Запускаем бинарный поиск только до последнего индекса

            // отрицательный int в приведенной выше строке

            nextEnd = getLastNegativeIndex(GetRow(M, i), 0, nextEnd);

            count += nextEnd + 1;

        }

        return count;

    }

    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;

    }

      

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

    public static void Main(String[] args)

    {

        int [,]M = { { -3, -2, -1, 1 },

                    { -2, 2, 3, 4 },

                    { 4, 5, 7, 8 } };

        int r = M.GetLength(0);

        int c = M.GetLength(1);

        Console.WriteLine(countNegative(M, r, c));

    }

}

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

Выход :

4

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

Эта статья предоставлена YK Sugishita и Rahul Jain . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Подсчет отрицательных чисел в матрице по столбцам и по строкам

0.00 (0%) 0 votes