Dada una array arr[] de tamaño N (que consta de duplicados), la tarea es verificar si la array dada se puede convertir en una array no decreciente al rotarla. Si no es posible hacerlo, escriba “ No ”. De lo contrario, escriba “ Sí ”.
Ejemplos:
Entrada: arr[] = {3, 4, 5, 1, 2}
Salida: Sí
Explicación: Después de 2 rotaciones a la derecha, la array arr[] se modifica a {1, 2, 3, 4, 5}Entrada: arr[] = {1, 2, 4, 3}
Salida: No
Enfoque: La idea se basa en el hecho de que se puede obtener un máximo de N arrays distintas rotando la array dada y verificando para cada array rotada individual, si es no decreciente o no. Siga los pasos a continuación para resolver el problema:
- Inicialice un vector , digamos v, y copie todos los elementos de la array original en él.
- Ordenar el vector v .
- Atraviese la array original y realice los siguientes pasos:
- Rotar de 1 en cada iteración.
- Si la array se vuelve igual al vector v , imprima » Sí «. De lo contrario, escriba “ No ”.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if a
// non-decreasing array can be obtained
// by rotating the original array
static void rotateArray(int[] arr, int N)
{
// Stores copy of original array
int[] v = arr;
// Sort the given vector
Arrays.sort(v);
// Traverse the array
for (int i = 1; i <= N; ++i) {
// Rotate the array by 1
int x = arr[N - 1];
i = N - 1;
while(i > 0){
arr[i] = arr[i - 1];
arr[0] = x;
i -= 1;
}
// If array is sorted
if (arr == v) {
System.out.print("YES");
return;
}
}
// If it is not possible to
// sort the array
System.out.print("NO");
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[] arr = { 3, 4, 5, 1, 2 };
// Size of the array
int N = arr.length;
// Function call to check if it is possible
// to make array non-decreasing by rotating
rotateArray(arr, N);
}
}
// This code is contributed by splevel62.
YES
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
¡ Consulte el artículo completo sobre Modificar una array dada a una array no decreciente por rotación 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