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.
Javascript
<script>
// JavaScript program to find shortest subarray which is
// unsorted.
// boolean function to check array elements
// are in increasing order or not
function increasing(a, n)
{
for (let i = 0; i < n - 1; i++)
if (a[i] >= a[i + 1])
return false;
return true;
}
// boolean function to check array elements
// are in decreasing order or not
function decreasing(arr, n)
{
for (let i = 0; i < n - 1; i++)
if (arr[i] < arr[i + 1])
return false;
return true;
}
function shortestUnsorted(a, 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
let ar = [7, 9, 10, 8, 11];
let n = ar.length;
document.write(shortestUnsorted(ar,n));
// This code is contributed by chinmoy1997pal.
</script>
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