Dada una matriz de tamaño m*n, ¿la tarea es contar todas las filas de una matriz que están ordenadas en orden estrictamente creciente o en orden estrictamente decreciente?
Ejemplos:
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
La idea es simple e implica dos recorridos de matriz.
- Recorra desde el lado izquierdo de la matriz para contar todas las filas que están en orden estrictamente creciente
- Atraviese desde el lado derecho de la matriz para contar todas las filas que están en orden estrictamente decreciente
A continuación se muestra la implementación de la idea anterior.
C++// C++ program to find number of sorted rows #include
// 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 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 of 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.
# 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 of 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 of 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# 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[ij + 1] <= mat[ij]) 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 // of element that are not in // decreasing order. int j; for (j = c - 1; j > 0; j--) if (mat[ij - 1] <= mat[ij]) 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.
<script> // Javascript program to find number of sorted rows let MAX = 100; // Function to count all sorted rows in a matrix function sortedCount(matrc) { 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 of 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 of 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>
// 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 of 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 // of 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. ?> Producción
3
Complejidad del tiempo: O(m*n)
Espacio auxiliar: O(1)
Si tiene otro enfoque optimizado para resolver este problema, compártalo en los comentarios.