Рубрики

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

Учитывая матрицу размера m * n, задача состоит в том, чтобы подсчитать все строки в матрице, которые отсортированы либо в строго возрастающем порядке, либо в строго убывающем порядке?

Примеры :

Input : m = 4,  n = 5
        mat[m][n] = 1 2 3 4 5
                    4 3 1 2 6
                    8 7 6 5 4
                    5 7 8 9 10
Output: 3 

Идея проста и включает в себя два обхода матрицы.
1) Пройдите по левой стороне матрицы, чтобы сосчитать все строки в строго возрастающем порядке.
2) Пройдите по правой стороне матрицы, чтобы сосчитать все строки в строго убывающем порядке.

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

C ++

// C ++ программа для поиска количества отсортированных строк
#include <bits/stdc++.h>
#define MAX 100

using namespace std;

  
// Функция для подсчета всех отсортированных строк в матрице

int sortedCount(int mat[][MAX], int r, int c)

{

    int result = 0; // Инициализировать результат

  

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

    // подсчитываем возрастающие строки заказа

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

    {

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

        // которые не в порядке возрастания.

        int j;

        for (j=0; j<c-1; j++)

            if (mat[i][j+1] <= mat[i][j])

                break;

  

        // Если цикл не прерывался (Все элементы

        // текущей строки были в порядке возрастания)

        if (j == c-1)

            result++;

    }

  

    // Начинаем с правой стороны матрицы

    // подсчитываем возрастающие строки заказа

    // слева в порядке убывания)

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

    {

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

        // которые не в порядке убывания.

        int j;

        for (j=c-1; j>0; j--)

            if (mat[i][j-1] <= mat[i][j])

                break;

  

        // Примечание c> 1 условие требуется для

        // уверен, что строка одного столбца не учитывается

        // дважды (обратите внимание, что строка одного столбца отсортирована

        // как в порядке возрастания, так и в порядке убывания)

        if (c > 1 && j == 0)

            result++;

    }

    return result;

}

  
// Драйвер программы для запуска дела

int main()

{

    int m = 4, n = 5;

    int mat[][MAX] = {{1, 2, 3, 4, 5},

                      {4, 3, 1, 2, 6},

                      {8, 7, 6, 5, 4},

                      {5, 7, 8, 9, 10}};

    cout << sortedCount(mat, m, n);

    return 0;

}

Джава

// Java программа для поиска количества отсортированных строк

  

class GFG {

      

    static int MAX = 100;

  

    // Функция для подсчета всех отсортированных строк в матрице

    static int sortedCount(int mat[][], int r, int c)

    {

        int result = 0; // Инициализировать результат

  

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

        // подсчитываем возрастающие строки заказа

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

              

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

            // которые не в порядке возрастания.

            int j;

            for (j = 0; j < c - 1; j++)

                if (mat[i][j + 1] <= mat[i][j])

                    break;

  

            // Если цикл не прерывался (Все элементы

            // текущей строки были в порядке возрастания)

            if (j == c - 1)

                result++;

        }

  

        // Начинаем с правой стороны матрицы

        // подсчитываем возрастающие строки заказа

        // слева в порядке убывания)

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

              

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

            // которые не в порядке убывания.

            int j;

            for (j = c - 1; j > 0; j--)

                if (mat[i][j - 1] <= mat[i][j])

                    break;

  

            // Примечание c> 1 условие требуется для

            // уверен, что строка одного столбца не учитывается

            // дважды (обратите внимание, что строка одного столбца отсортирована

            // как в порядке возрастания, так и в порядке убывания)

            if (c > 1 && j == 0)

                result++;

        }

        return result;

    }

      

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

    public static void main(String arg[])

    {

        int m = 4, n = 5;

        int mat[][] = { { 1, 2, 3, 4, 5 },

                        { 4, 3, 1, 2, 6 },

                        { 8, 7, 6, 5, 4 },

                        { 5, 7, 8, 9, 10 } };

        System.out.print(sortedCount(mat, m, n));

    }

}

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

питон

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

def sortedCount(mat, r, c):

      

    result = 0

      

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

    # считать возрастающие строки заказа

    for i in range(r):

          

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

        # которые не в порядке возрастания.

        j = 0

        for j in range(c - 1):

            if mat[i][j + 1] <= mat[i][j]:

                break

      

        # Если цикл не прерывался (Все элементы

        # текущего ряда были в порядке возрастания)

        if j == c - 2:

            result += 1

  

    # Начать с правой стороны матрицы до

    # количество увеличивающихся строк заказа (ссылка

    # слева это в порядке убывания)

    for i in range(0, r):

  

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

        # которые не в порядке убывания.

        j = 0

        for j in range(c - 1, 0, -1):

            if mat[i][j - 1] <= mat[i][j]:

                break

          

        # Примечание c> 1 условие требуется для

        # убедитесь, что один столбец строки

        # не учитывается дважды (обратите внимание, что

        # строка одного столбца сортируется как

        # в порядке возрастания и убывания)

        if c > 1 and j == 1:

            result += 1

      

    return result     

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

m, n = 4, 5

  

mat = [[1, 2, 3, 4, 5],

       [4, 3, 1, 2, 6],

       [8, 7, 6, 5, 4],

       [5, 7, 8, 9, 10]]

  

print(sortedCount(mat, m, n))

  
# Этот код предоставлен
# Мохит Кумар 29 (IIIT Гвалиор)

C #

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

using System;

  

class GFG {

      
// static int MAX = 100;

  

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

    // матрица

    static int sortedCount(int [,]mat, int r,

                                       int c)

    {

        int result = 0; // Инициализировать результат

  

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

        // подсчитываем возрастающие строки заказа

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

              

            // Проверяем, есть ли пара

            // элемент, которого нет в

            // увеличение порядка.

            int j;

            for (j = 0; j < c - 1; j++)

                if (mat[i,j + 1] <= mat[i,j])

                    break;

  

            // Если цикл не прерывался (Все

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

            // в порядке возрастания)

            if (j == c - 1)

                result++;

        }

  

        // Начинаем с правой стороны матрицы

        // для подсчета возрастающих строк заказа

        // (ссылка слева это в

        // убывающий порядок)

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

              

            // Проверяем, есть ли пара

            // элемент ofs, которого нет в

            // убывающий порядок.

            int j;

            for (j = c - 1; j > 0; j--)

                if (mat[i,j - 1] <= mat[i,j])

                    break;

  

            // Примечание c> 1 условие

            // необходимо убедиться, что

            // строка одного столбца не

            // посчитаны дважды (обратите внимание, что

            // строка одного столбца сортируется

            // как в увеличении, так и

            // убывающий порядок)

            if (c > 1 && j == 0)

                result++;

        }

        return result;

    }

      

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

    public static void Main()

    {

        int m = 4, n = 5;

        int [,]mat = { { 1, 2, 3, 4, 5 },

                       { 4, 3, 1, 2, 6 },

                       { 8, 7, 6, 5, 4 },

                       { 5, 7, 8, 9, 10 } };

                         

        Console.WriteLine(

                   sortedCount(mat, m, n));

    }

}

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

PHP

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

  

$MAX = 100;

  
// Функция для подсчета всех
// отсортированные строки в матрице

function sortedCount($mat

                     $r, $c)

{

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

    $result = 0; 

  

    // Начинаем с левой стороны

    // матрица для увеличения счета

    // порядок строк

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

    {

        // Проверяем, есть ли

        // пара элементов, которые

        // не в порядке возрастания.

        $j;

        for ($j = 0; $j < $c - 1; $j++)

            if ($mat[$i][$j + 1] <= $mat[$i][$j])

                break;

  

        // Если цикл не прерывался

        // (Все элементы текущего

        // строки были в порядке возрастания)

        if ($j == $c - 1)

            $result++;

    }

  

    // Начинаем с правой стороны

    // матрица для увеличения счета

    // упорядочить строки (ссылка слева

    // это в порядке убывания)

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

    {

        // Проверяем, есть ли пара

        // элемент ofs который не

        // в порядке убывания.

        $j;

        for ($j = $c - 1; $j > 0; $j--)

            if ($mat[$i][$j - 1] <= $mat[$i][$j])

                break;

  

        // Примечание c> 1 условие

        // необходимо убедиться, что

        // строка одного столбца не

        // посчитаны дважды (обратите внимание, что

        // строка одного столбца сортируется

        // как в увеличении, так и

        // убывающий порядок)

        if ($c > 1 && $j == 0)

            $result++;

    }

    return $result;

}

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

$m = 4; $n = 5;

$mat = array(array(1, 2, 3, 4, 5),

             array(4, 3, 1, 2, 6),

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

             array(5, 7, 8, 9, 10));

echo sortedCount($mat, $m, $n);

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


Выход :

3

Сложность времени: O (m * n)
Вспомогательное пространство: O (1)

Если у вас есть другой оптимизированный подход к решению этой проблемы, пожалуйста, поделитесь в комментариях.

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes