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.
PHP
<?php
// php program to find shortest
// subarray which is unsorted.
// bool function for checking an
// array elements are in increasing.
function increasing($a, $n)
{
for ( $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.
function decreasing($a, $n)
{
for ($i = 0; $i < $n - 1; $i++)
if ($a[$i] < $a[$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
$ar = array( 7, 9, 10, 8, 11 );
$n = sizeof($ar);
echo shortestUnsorted($ar, $n);
// This code is contributed by
// nitin mittal.
?>
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