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.
Java
// JAVA program to find shortest subarray which is
// unsorted.
import java.util.*;
import java.io.*;
class GFG {
// boolean function to check array elements
// are in increasing order or not
public static boolean increasing(int a[],int n)
{
for (int 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
public static boolean decreasing(int arr[],int n)
{
for (int i = 0; i < n - 1; i++)
if (arr[i] < arr[i + 1])
return false;
return true;
}
public static 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 program
public static void main (String[] args) {
int ar[] = new int[]{7, 9, 10, 8, 11};
int n = ar.length;
System.out.println(shortestUnsorted(ar,n));
}
}
// This code is contributed by Akash Singh.
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