Dada una array de enteros. La tarea es encontrar la bitonicidad de la array dada.
La bitonicidad de una array arr[] se puede definir como:
B[i] = 0, if i = 0. = B[i-1] + 1, if arr[i] > arr[i-1] = B[i-1] - 1, if arr[i] < arr[i-1] = B[i-1], if arr[i] = arr[i-1] Bitonicity will be last element of array B[].
Ejemplos :
Input : arr[] = {1, 2, 3, 4, 5} Output : 4 Input : arr[] = {1, 4, 5, 3, 2} Output : 0
Dado que la Bitonicidad de un arreglo arr[] se puede definir como:
B[i] = 0, if i = 0. = B[i-1] + 1, if arr[i] > arr[i-1] = B[i-1] - 1, if arr[i] < arr[i-1] = B[i-1], if arr[i] = arr[i-1] Bitonicity will be last element of array B[].
De la expresión anterior se puede deducir que:
- La bitonicidad de la array es inicialmente 0.
- Aumenta en 1 al pasar al siguiente elemento si el siguiente elemento es mayor que el anterior.
- Disminuye en 1 al pasar al siguiente elemento si el siguiente elemento es mayor que el anterior.
La idea es tomar una variable y comenzar a recorrer la array, si el siguiente elemento es mayor que el actual, incremente bt en 1 y si el siguiente elemento es más pequeño que el actual, disminuya bt en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find bitonicity // of an array #include <iostream> using namespace std; // Function to find the bitonicity // of an array int findBitonicity(int arr[], int n) { int bt = 0; for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) bt++; else if (arr[i] < arr[i - 1]) bt--; } return bt; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 4, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Bitonicity = " << findBitonicity(arr, n); return 0; }
Java
// Java program to find bitonicity // of an array import java.util.*; import java.lang.*; class GFG { // Function to find the bitonicity // of an array static int findBitonicity(int[] arr, int n) { int bt = 0; for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) bt++; else if (arr[i] < arr[i - 1]) bt--; } return bt; } // Driver Code public static void main(String args[]) { int arr[] = { 1, 2, 3, 4, 5, 6, 4, 3 }; int n = arr.length; System.out.print("Bitonicity = " + findBitonicity(arr, n)); } } // This code is contributed // by Akanksha Rai
Python3
# Python3 program to find bitonicity # of an array # Function to find the bitonicity # of an array def findBitonicity(arr, n): bt = 0 for i in range(1, n, 1): if (arr[i] > arr[i - 1]): bt += 1 elif (arr[i] < arr[i - 1]): bt -= 1 return bt # Driver Code if __name__ == '__main__': arr = [1, 2, 3, 4, 5, 6, 4, 3] n = len(arr) print("Bitonicity =", findBitonicity(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find bitonicity // of an array using System; class GFG { // Function to find the bitonicity // of an array static int findBitonicity(int[] arr, int n) { int bt = 0; for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) bt++; else if (arr[i] < arr[i - 1]) bt--; } return bt; } // Driver Code public static void Main() { int[] arr = { 1, 2, 3, 4, 5, 6, 4, 3 }; int n = arr.Length; Console.Write("Bitonicity = " + findBitonicity(arr, n)); } } // This code is contributed // by Akanksha Rai
PHP
<?php // PHP program to find bitonicity // of an array // Function to find the bitonicity // of an array function findBitonicity(&$arr, $n) { $bt = 0; for ($i = 1; $i < $n; $i++) { if ($arr[$i] > $arr[$i - 1]) $bt++; else if ($arr[$i] < $arr[$i - 1]) $bt--; } return $bt; } // Driver Code $arr = array(1, 2, 3, 4, 5, 6, 4, 3 ); $n = sizeof($arr); echo ("Bitonicity = "); echo findBitonicity($arr, $n); // This code is contributed // by Shivi_Aggarwal ?>
Javascript
<script> // Javascript program to find bitonicity // of an array // Function to find the bitonicity // of an array function findBitonicity(arr , n) { var bt = 0; for (i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) bt++; else if (arr[i] < arr[i - 1]) bt--; } return bt; } // Driver Code var arr = [ 1, 2, 3, 4, 5, 6, 4, 3 ]; var n = arr.length; document.write("Bitonicity = " + findBitonicity(arr, n)); // This code contributed by gauravrajput1 </script>
Bitonicity = 3
Complejidad de tiempo: O (N), ya que estamos usando un ciclo para atravesar N veces para encontrar la bitonicidad de la array.
Espacio auxiliar: O(1), ya que no estamos usando ninguna complejidad de espacio adicional.