Dada una array m[][] , la tarea es comprobar si la array dada es bitónica inversa o no. Si la array dada es Bitónica inversa, imprima Sí . De lo contrario , imprima No.
Si todas las filas y las columnas de la array dada tienen elementos en uno de los siguientes órdenes:
- Estrictamente creciente
- estrictamente decreciente
- Estrictamente decreciente seguido de estrictamente creciente
Entonces se dice que la array dada es una array bitónica inversa
Ejemplos :
Entrada: m[][] = {{2, 3, 4}, {1, 2, 3}, {4, 5, 6} }
Salida: Sí
Explicación:
Todas las filas de la array dada forman una secuencia creciente.
Todas las columnas de la array dada {2, 1, 4}, {3, 2, 5}, {4, 3, 6} forman una secuencia decreciente seguida de una secuencia creciente.
Por lo tanto, la array es bitónica inversa.
Entrada: m[][] = {{1, 2, 3}, {4, 5, 6}, {2, 5, 4}}
Salida: No
Explicación:
Dado que la columna {1, 4, 2} no satisface cualquiera de las tres condiciones, la array dada no es bitónica inversa.
Enfoque :
siga los pasos a continuación para resolver el problema:
- Verifique los elementos de cada fila de la array uno por uno, si forma una secuencia bitónica inversa o no. Si se encuentra que alguna fila no es bitónica inversa , imprima No.
- Del mismo modo, verifique los elementos de cada columna uno por uno, si forma una secuencia bitónica inversa o no. Si se encuentra que alguna fila no es bitónica inversa , imprima No.
- Si se encuentra que todas las filas y columnas son bitónicas inversas , imprima Sí.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to check if a // matrix is Reverse Bitonic or not #include <bits/stdc++.h> using namespace std; const int N = 3, M = 3; // Function to check if an // array is Reverse Bitonic or not bool checkReverseBitonic(int arr[], int n) { int i, j, f = 0; // Check for decreasing sequence for (i = 1; i < n; i++) { if (arr[i] < arr[i - 1]) continue; if (arr[i] == arr[i - 1]) return false; else { f = 1; break; } } if (i == n) return true; // Check for increasing sequence for (j = i + 1; j < n; j++) { if (arr[j] > arr[j - 1]) continue; if (arr[i] == arr[i - 1]) return false; else { if (f == 1) return false; } } return true; } // Function to check whether given // matrix is bitonic or not void check(int arr[N][M]) { int f = 0; // Check row-wise for (int i = 0; i < N; i++) { if (!checkReverseBitonic(arr[i], M)) { cout << "No" << endl; return; } } // Check column wise for (int i = 0; i < N; i++) { // Generate an array // consisting of elements // of the current column int temp[N]; for (int j = 0; j < N; j++) { temp[j] = arr[j][i]; } if (!checkReverseBitonic(temp, N)) { cout << "No" << endl; return; } } cout << "Yes"; } // Driver Code int main() { int m[N][M] = { { 2, 3, 4 }, { 1, 2, 3 }, { 4, 5, 6 } }; check(m); return 0; }
Java
// Java Program to check if a // matrix is Reverse Bitonic or not import java.util.*; class GFG{ static int N = 3, M = 3; // Function to check if an // array is Reverse Bitonic or not static boolean checkReverseBitonic(int arr[], int n) { int i, j, f = 0; // Check for decreasing sequence for (i = 1; i < n; i++) { if (arr[i] < arr[i - 1]) continue; if (arr[i] == arr[i - 1]) return false; else { f = 1; break; } } if (i == n) return true; // Check for increasing sequence for (j = i + 1; j < n; j++) { if (arr[j] > arr[j - 1]) continue; if (arr[i] == arr[i - 1]) return false; else { if (f == 1) return false; } } return true; } // Function to check whether given // matrix is bitonic or not static void check(int arr[][]) { int f = 0; // Check row-wise for (int i = 0; i < N; i++) { if (!checkReverseBitonic(arr[i], M)) { System.out.print("No" + "\n"); return; } } // Check column wise for (int i = 0; i < N; i++) { // Generate an array // consisting of elements // of the current column int temp[] = new int[N]; for (int j = 0; j < N; j++) { temp[j] = arr[j][i]; } if (!checkReverseBitonic(temp, N)) { System.out.print("No" + "\n"); return; } } System.out.print("Yes"); } // Driver Code public static void main(String[] args) { int m[][] = { { 2, 3, 4 }, { 1, 2, 3 }, { 4, 5, 6 } }; check(m); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to check if a # matrix is Reverse Bitonic or not N = 3 M = 3 # Function to check if an # array is Reverse Bitonic or not def checkReverseBitonic(arr, n): f = 0 # Check for decreasing sequence for i in range(1, n): if (arr[i] < arr[i - 1]): continue if (arr[i] == arr[i - 1]): return False else: f = 1 break if (i == n): return True # Check for increasing sequence for j in range(i + 1, n): if (arr[j] > arr[j - 1]): continue if (arr[i] == arr[i - 1]): return False else: if (f == 1): return False return True # Function to check whether given # matrix is bitonic or not def check(arr): f = 0 # Check row-wise for i in range (N): if (not checkReverseBitonic(arr[i], M)): print("No") return # Check column wise for i in range(N): # Generate an array # consisting of elements # of the current column temp = [0] * N for j in range(N): temp[j] = arr[j][i] if (not checkReverseBitonic(temp, N)): print("No") return print("Yes") # Driver Code if __name__ == "__main__": m = [ [ 2, 3, 4 ], [ 1, 2, 3 ], [ 4, 5, 6 ] ] check(m) # This code is contributed by chitranayal
C#
// C# Program to check if a // matrix is Reverse Bitonic or not using System; class GFG{ static int N = 3, M = 3; // Function to check if an // array is Reverse Bitonic or not static bool checkReverseBitonic(int []arr, int n) { int i, j, f = 0; // Check for decreasing sequence for (i = 1; i < n; i++) { if (arr[i] < arr[i - 1]) continue; if (arr[i] == arr[i - 1]) return false; else { f = 1; break; } } if (i == n) return true; // Check for increasing sequence for (j = i + 1; j < n; j++) { if (arr[j] > arr[j - 1]) continue; if (arr[i] == arr[i - 1]) return false; else { if (f == 1) return false; } } return true; } // Function to check whether given // matrix is bitonic or not static void check(int [,]arr) { // Check row-wise for (int i = 0; i < N; i++) { if (!checkReverseBitonic(GetRow(arr, i), M)) { Console.Write("No" + "\n"); return; } } // Check column wise for (int i = 0; i < N; i++) { // Generate an array // consisting of elements // of the current column int []temp = new int[N]; for (int j = 0; j < N; j++) { temp[j] = arr[j,i]; } if (!checkReverseBitonic(temp, N)) { Console.Write("No" + "\n"); return; } } Console.Write("Yes"); } 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; } // Driver Code public static void Main(String[] args) { int [,]m = {{ 2, 3, 4 }, { 1, 2, 3 }, { 4, 5, 6 }}; check(m); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Java script Program to check if a // matrix is Reverse Bitonic or not let N = 3, M = 3; // Function to check if an // array is Reverse Bitonic or not function checkReverseBitonic(arr,n) { let i, j, f = 0; // Check for decreasing sequence for (i = 1; i < n; i++) { if (arr[i] < arr[i - 1]) continue; if (arr[i] == arr[i - 1]) return false; else { f = 1; break; } } if (i == n) return true; // Check for increasing sequence for (j = i + 1; j < n; j++) { if (arr[j] > arr[j - 1]) continue; if (arr[i] == arr[i - 1]) return false; else { if (f == 1) return false; } } return true; } // Function to check whether given // matrix is bitonic or not function check(arr) { let f = 0; // Check row-wise for (let i = 0; i < N; i++) { if (!checkReverseBitonic(arr[i], M)) { document.write("No" + "<br>"); return; } } // Check column wise for (let i = 0; i < N; i++) { // Generate an array // consisting of elements // of the current column let temp= [N]; for (let j = 0; j < N; j++) { temp[j] = arr[j][i]; } if (!checkReverseBitonic(temp, N)) { document.write("No" + "<br>"); return; } } document.write("Yes"); } // Driver Code let m = [[ 2, 3, 4 ], [ 1, 2, 3 ], [ 4, 5, 6 ]]; check(m); // This code is contributed by sravan kumar </script>
Yes
Complejidad temporal: O(N × M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA