Se da una array de n longitud, y el problema es que tenemos que encontrar la longitud de la subarray desordenada más corta {ni creciente ni decreciente} en una array dada.
Ejemplos:
Input : n = 5
7 9 10 8 11
Output : 3
Explanation : 9 10 8 unordered sub array.
Input : n = 5
1 2 3 4 5
Output : 0
Explanation : Array is in increasing order.
La idea se basa en el hecho de que el tamaño del subarreglo más corto sería 0 o 3. Tenemos que verificar que el elemento del arreglo esté aumentando o disminuyendo, si todos los elementos del arreglo están aumentando o disminuyendo, entonces la longitud del subarreglo más corto es 0, Y si el elemento de la array no sigue el aumento o la disminución, entonces su longitud más corta es 3.
C++
// CPP program to find shortest subarray which is
// unsorted.
#include <bits/stdc++.h>
using namespace std;
// bool function for checking an array elements
// are in increasing.
bool increasing(int a[], int n)
{
for (int i = 0; i < n - 1; i++)
if (a[i] >= a[i + 1])
return false;
return true;
}
// bool function for checking an array
// elements are in decreasing.
bool decreasing(int a[], int n)
{
for (int i = 0; i < n - 1; i++)
if (a[i] < a[i + 1])
return false;
return true;
}
int shortestUnsorted(int a[], int n)
{
// increasing and decreasing are two functions.
// if function return true value then print
// 0 otherwise 3.
if (increasing(a, n) == true ||
decreasing(a, n) == true)
return 0;
else
return 3;
}
// Driver code
int main()
{
int ar[] = { 7, 9, 10, 8, 11 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << shortestUnsorted(ar, n);
return 0;
}
3
Complejidad temporal: O(n) donde n es la longitud de la array.
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre el subarreglo desordenado más corto para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA