Comprobar si una array es bitónica inversa o no

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 . 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:
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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *