Dada una array de N enteros distintos. La tarea es escribir un programa para verificar si esta array está ordenada y girada en sentido contrario a las agujas del reloj. Una array ordenada no se considera ordenada y rotada, es decir, debe haber al menos una rotación.
Ejemplos :
Input : arr[] = { 3, 4, 5, 1, 2 }
Output : YES
The above array is sorted and rotated.
Sorted array: {1, 2, 3, 4, 5}.
Rotating this sorted array clockwise
by 3 positions, we get: { 3, 4, 5, 1, 2}
Input: arr[] = {7, 9, 11, 12, 5}
Output: YES
Input: arr[] = {1, 2, 3}
Output: NO
Input: arr[] = {3, 4, 6, 1, 2, 5}
Output: NO
Enfoque :
- Encuentre el elemento mínimo en la array.
- Ahora, si se ordena la array y luego se giran todos los elementos antes del elemento mínimo estarán en orden creciente y todos los elementos después del elemento mínimo también estarán en orden creciente.
- Compruebe si todos los elementos antes del elemento mínimo están en orden creciente.
- Compruebe si todos los elementos después del elemento mínimo están en orden creciente.
- Compruebe si el último elemento de la array es más pequeño que el elemento inicial.
- Si se cumplen las tres condiciones anteriores, imprima SÍ ; de lo contrario, imprima NO .
A continuación se muestra la implementación de la idea anterior:
Javascript
<script>
// Javascript program to check if an
// array is sorted and rotated
// clockwise
// Function to check if an array is
// sorted and rotated clockwise
function checkIfSortRotated(arr, n)
{
let minEle = Number.MAX_VALUE;
// int maxEle = int.MinValue;
let minIndex = -1;
// Find the minimum element
// and it's index
for (let i = 0; i < n; i++) {
if (arr[i] < minEle) {
minEle = arr[i];
minIndex = i;
}
}
let flag1 = true;
// Check if all elements before
// minIndex are in increasing order
for (let i = 1; i < minIndex; i++) {
if (arr[i] < arr[i - 1]) {
flag1 = false;
break;
}
}
let flag2 = true;
// Check if all elements after
// minIndex are in increasing order
for (let i = minIndex + 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
flag2 = false;
break;
}
}
// Check if last element of the array
// is smaller than the element just
// before the element at minIndex
// starting element of the array
// for arrays like [3,4,6,1,2,5] - not circular
// array
if (flag1 && flag2 && (arr[n - 1] < arr[0]))
document.write("YES");
else
document.write("NO");
}
let arr = [ 3, 4, 5, 1, 2 ];
let n = arr.length;
// Function Call
checkIfSortRotated(arr, n);
// This code is contributed by mukesh07.
</script>
YES
Complejidad de tiempo: O(N), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Consulte el artículo completo sobre Comprobar si una array está ordenada y rotada 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