计算矩阵中所有已排序的行-yiteyi-C++库

给定一个m*n大小的矩阵，任务是计算矩阵中按严格递增顺序或严格递减顺序排序的所有行？ 例如：

null

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 10Output: 3

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

这个想法很简单，涉及矩阵的两次遍历。 1）从矩阵的左侧遍历，以计算矩阵中的所有行 严格增加订单 2）从矩阵的右侧遍历，以计算矩阵中的所有行 严格降序 下面是上述想法的实现。

C++

                         // C++ program to find number of sorted rows                       
                         #include <bits/stdc++.h>                       
                         #define MAX 100                       
                         using                                     namespace                                     std;                       
           
                         // Function to count all sorted rows in a matrix                       
                         int                                     sortedCount(                                     int                                     mat[][MAX],                                     int                                     r,                                     int                                     c)                       
                         {                       
                                                 int                                     result = 0;                                     // Initialize result                       
           
                                                 // Start from left side of matrix to                       
                                                 // count increasing order rows                       
                                                 for                                     (                                     int                                     i=0; i<r; i++)                       
                                                 {                       
                                                 // Check if there is any pair ofs element                       
                                                 // that are  not in increasing order.                       
                                                 int                                     j;                       
                                                 for                                     (j=0; j<c-1; j++)                       
                                                 if                                     (mat[i][j+1] <= mat[i][j])                       
                                                 break                                     ;                       
           
                                                 // If the loop didn't break (All elements                       
                                                 // of current row were in increasing order)                       
                                                 if                                     (j == c-1)                       
                                                 result++;                       
                                                 }                       
           
                                                 // Start from right side of matrix to                       
                                                 // count increasing order rows ( reference                       
                                                 // to left these are in decreasing order )                       
                                                 for                                     (                                     int                                     i=0; i<r; i++)                       
                                                 {                       
                                                 // Check if there is any pair ofs element                       
                                                 // that are  not in decreasing order.                       
                                                 int                                     j;                       
                                                 for                                     (j=c-1; j>0; j--)                       
                                                 if                                     (mat[i][j-1] <= mat[i][j])                       
                                                 break                                     ;                       
           
                                                 // Note c > 1 condition is required to make                       
                                                 // sure that a single column row is not counted                       
                                                 // twice (Note that a single column row is sorted                       
                                                 // both in increasing and decreasing order)                       
                                                 if                                     (c > 1 && j == 0)                       
                                                 result++;                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver program to run the case                       
                         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

                         // Java program to find number of sorted rows                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     MAX =                                     100                                     ;                       
           
                                                 // Function to count all sorted rows in a matrix                       
                                                 static                                     int                                     sortedCount(                                     int                                     mat[][],                                     int                                     r,                                     int                                     c)                       
                                                 {                       
                                                 int                                     result =                                     0                                     ;                                     // Initialize result                       
           
                                                 // Start from left side of matrix to                       
                                                 // count increasing order rows                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < r; i++) {                       
                                   
                                                 // Check if there is any pair ofs element                       
                                                 // that are not in increasing order.                       
                                                 int                                     j;                       
                                                 for                                     (j =                                     0                                     ; j < c -                                     1                                     ; j++)                       
                                                 if                                     (mat[i][j +                                     1                                     ] <= mat[i][j])                       
                                                 break                                     ;                       
           
                                                 // If the loop didn't break (All elements                       
                                                 // of current row were in increasing order)                       
                                                 if                                     (j == c -                                     1                                     )                       
                                                 result++;                       
                                                 }                       
           
                                                 // Start from right side of matrix to                       
                                                 // count increasing order rows ( reference                       
                                                 // to left these are in decreasing order )                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < r; i++) {                       
                                   
                                                 // Check if there is any pair ofs element                       
                                                 // that are not in decreasing order.                       
                                                 int                                     j;                       
                                                 for                                     (j = c -                                     1                                     ; j >                                     0                                     ; j--)                       
                                                 if                                     (mat[i][j -                                     1                                     ] <= mat[i][j])                       
                                                 break                                     ;                       
           
                                                 // Note c > 1 condition is required to make                       
                                                 // sure that a single column row is not counted                       
                                                 // twice (Note that a single column row is sorted                       
                                                 // both in increasing and decreasing order)                       
                                                 if                                     (c >                                     1                                     && j ==                                     0                                     )                       
                                                 result++;                       
                                                 }                       
                                                 return                                     result;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 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));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

python

                         # Python3 program to find number                       
                         # of sorted rows                       
                         def                                     sortedCount(mat, r, c):                       
                                   
                                                 result                                     =                                     0                       
                                   
                                                 # Start from left side of matrix to                       
                                                 # count increasing order rows                       
                                                 for                                     i                                     in                                     range                                     (r):                       
                                   
                                                 # Check if there is any pair ofs element                       
                                                 # that are not in increasing order.                       
                                                 j                                     =                                     0                       
                                                 for                                     j                                     in                                     range                                     (c                                     -                                     1                                     ):                       
                                                 if                                     mat[i][j                                     +                                     1                                     ] <                                     =                                     mat[i][j]:                       
                                                 break                       
                                   
                                                 # If the loop didn't break (All elements                       
                                                 # of current row were in increasing order)                       
                                                 if                                     j                                     =                                     =                                     c                                     -                                     2                                     :                       
                                                 result                                     +                                     =                                     1                       
           
                                                 # Start from right side of matrix to                       
                                                 # count increasing order rows ( reference                       
                                                 # to left these are in decreasing order )                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , r):                       
           
                                                 # Check if there is any pair ofs element                       
                                                 # that are not in decreasing order.                       
                                                 j                                     =                                     0                       
                                                 for                                     j                                     in                                     range                                     (c                                     -                                     1                                     ,                                     0                                     ,                                     -                                     1                                     ):                       
                                                 if                                     mat[i][j                                     -                                     1                                     ] <                                     =                                     mat[i][j]:                       
                                                 break                       
                                   
                                                 # Note c > 1 condition is required to                       
                                                 # make sure that a single column row                       
                                                 # is not counted twice (Note that a                       
                                                 # single column row is sorted both                       
                                                 # in increasing and decreasing order)                       
                                                 if                                     c >                                     1                                     and                                     j                                     =                                     =                                     1                                     :                       
                                                 result                                     +                                     =                                     1                       
                                   
                                                 return                                     result                       
           
                         # Driver code                       
                         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))                       
           
                         # This code is contributed by                       
                         # Mohit kumar 29 (IIIT gwalior)                       

C#

                         // C# program to find number of sorted rows                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                         // static int MAX = 100;                       
           
                                                 // Function to count all sorted rows in                       
                                                 // a matrix                       
                                                 static                                     int                                     sortedCount(                                     int                                     [,]mat,                                     int                                     r,                       
                                                 int                                     c)                       
                                                 {                       
                                                 int                                     result = 0;                                     // Initialize result                       
           
                                                 // Start from left side of matrix to                       
                                                 // count increasing order rows                       
                                                 for                                     (                                     int                                     i = 0; i < r; i++) {                       
                                   
                                                 // Check if there is any pair of                       
                                                 // element that are not in                       
                                                 // increasing order.                       
                                                 int                                     j;                       
                                                 for                                     (j = 0; j < c - 1; j++)                       
                                                 if                                     (mat[i,j + 1] <= mat[i,j])                       
                                                 break                                     ;                       
           
                                                 // If the loop didn't break (All                       
                                                 // elements of current row were                       
                                                 // in increasing order)                       
                                                 if                                     (j == c - 1)                       
                                                 result++;                       
                                                 }                       
           
                                                 // Start from right side of matrix                       
                                                 // to count increasing order rows                       
                                                 // ( reference to left these are in                       
                                                 // decreasing order )                       
                                                 for                                     (                                     int                                     i = 0; i < r; i++) {                       
                                   
                                                 // Check if there is any pair                       
                                                 // ofs element that are not in                       
                                                 // decreasing order.                       
                                                 int                                     j;                       
                                                 for                                     (j = c - 1; j > 0; j--)                       
                                                 if                                     (mat[i,j - 1] <= mat[i,j])                       
                                                 break                                     ;                       
           
                                                 // Note c > 1 condition is                       
                                                 // required to make sure that a                       
                                                 // single column row is not                       
                                                 // counted twice (Note that a                       
                                                 // single column row is sorted                       
                                                 // both in increasing and                       
                                                 // decreasing order)                       
                                                 if                                     (c > 1 && j == 0)                       
                                                 result++;                       
                                                 }                       
                                                 return                                     result;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 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));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

PHP

                         <?php                       
                         // PHP program to find                       
                         // number of sorted rows                       
           
                         $MAX                                     = 100;                       
           
                         // Function to count all                       
                         // sorted rows in a matrix                       
                         function                                     sortedCount(                                     $mat                                     ,                       
                                                 $r                                     ,                                     $c                                     )                       
                         {                       
                                                 // Initialize result                       
                                                 $result                                     = 0;                       
           
                                                 // Start from left side of                       
                                                 // matrix to count increasing                       
                                                 // order rows                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $r                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // Check if there is any                       
                                                 // pair ofs element that                       
                                                 // are not in increasing order.                       
                                                 $j                                     ;                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <                                     $c                                     - 1;                                     $j                                     ++)                       
                                                 if                                     (                                     $mat                                     [                                     $i                                     ][                                     $j                                     + 1] <=                                     $mat                                     [                                     $i                                     ][                                     $j                                     ])                       
                                                 break                                     ;                       
           
                                                 // If the loop didn't break                       
                                                 // (All elements of current                       
                                                 // row were in increasing order)                       
                                                 if                                     (                                     $j                                     ==                                     $c                                     - 1)                       
                                                 $result                                     ++;                       
                                                 }                       
           
                                                 // Start from right side of                       
                                                 // matrix to count increasing                       
                                                 // order rows ( reference to left                       
                                                 // these are in decreasing order )                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $r                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // Check if there is any pair                       
                                                 // ofs element that are not                       
                                                 // in decreasing order.                       
                                                 $j                                     ;                       
                                                 for                                     (                                     $j                                     =                                     $c                                     - 1;                                     $j                                     > 0;                                     $j                                     --)                       
                                                 if                                     (                                     $mat                                     [                                     $i                                     ][                                     $j                                     - 1] <=                                     $mat                                     [                                     $i                                     ][                                     $j                                     ])                       
                                                 break                                     ;                       
           
                                                 // Note c > 1 condition is                       
                                                 // required to make sure that                       
                                                 // a single column row is not                       
                                                 // counted twice (Note that a                       
                                                 // single column row is sorted                       
                                                 // both in increasing and                       
                                                 // decreasing order)                       
                                                 if                                     (                                     $c                                     > 1 &&                                     $j                                     == 0)                       
                                                 $result                                     ++;                       
                                                 }                       
                                                 return                                     $result                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $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                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to find number of sorted rows                       
                                   
                                                 let MAX = 100;                       
                                   
                                                 // Function to count all sorted rows in a matrix                       
                                                 function                                     sortedCount(mat,r,c)                       
                                                 {                       
                                                 let result = 0;                                     // Initialize result                       
                                   
                                                 // Start from left side of matrix to                       
                                                 // count increasing order rows                       
                                                 for                                     (let i = 0; i < r; i++) {                       
                                   
                                                 // Check if there is any pair ofs element                       
                                                 // that are not in increasing order.                       
                                                 let j;                       
                                                 for                                     (j = 0; j < c - 1; j++)                       
                                                 if                                     (mat[i][j + 1] <= mat[i][j])                       
                                                 break                                     ;                       
                                   
                                                 // If the loop didn't break (All elements                       
                                                 // of current row were in increasing order)                       
                                                 if                                     (j == c - 1)                       
                                                 result++;                       
                                                 }                       
                                   
                                                 // Start from right side of matrix to                       
                                                 // count increasing order rows ( reference                       
                                                 // to left these are in decreasing order )                       
                                                 for                                     (let i = 0; i < r; i++) {                       
                                   
                                                 // Check if there is any pair ofs element                       
                                                 // that are not in decreasing order.                       
                                                 let j;                       
                                                 for                                     (j = c - 1; j > 0; j--)                       
                                                 if                                     (mat[i][j - 1] <= mat[i][j])                       
                                                 break                                     ;                       
                                   
                                                 // Note c > 1 condition is required to make                       
                                                 // sure that a single column row is not counted                       
                                                 // twice (Note that a single column row is sorted                       
                                                 // both in increasing and decreasing order)                       
                                                 if                                     (c > 1 && j == 0)                       
                                                 result++;                       
                                                 }                       
                                                 return                                     result;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 let m = 4, n = 5;                       
                                   
                                                 let mat = [[1, 2, 3, 4, 5],                       
                                                 [4, 3, 1, 2, 6],                       
                                                 [8, 7, 6, 5, 4],                       
                                                 [5, 7, 8, 9, 10]]                       
                                                 document.write(sortedCount(mat, m, n))                       
           
                                   
                                                 // This code is contributed by unknown2108                       
                         </script>                       

输出：

时间复杂性： O（m*n） 辅助空间： O（1）如果你有其他优化方法来解决这个问题，那么请在评论中分享。本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章