Programa Java para contar las rotaciones requeridas para generar una array ordenada

Dada una array arr[] , la tarea es encontrar el número de rotaciones requeridas para convertir la array dada a una forma ordenada.
Ejemplos:

Entrada: arr[] = {4, 5, 1, 2, 3} 
Salida: 2 
Explicación: 
array ordenada {1, 2, 3, 4, 5} después de 2 rotaciones en sentido contrario a las agujas del reloj.

Entrada: arr[] = {2, 1, 2, 2, 2} 
Salida: 1 
Explicación: 
array ordenada {1, 2, 2, 2, 2} después de 1 rotación en sentido contrario a las agujas del reloj.

Enfoque ingenuo:
para resolver el problema mencionado anteriormente, la primera observación es que si tenemos n elementos en la array, luego de ordenar, el elemento más grande está en (n – 1) la posición ^th . Después de k número de rotaciones en sentido contrario a las agujas del reloj, el elemento más grande estará en el índice (k – 1) (k ^-ésimo elemento desde el inicio). Otra cosa a tener en cuenta aquí es que, después de la rotación, el siguiente elemento del elemento más grande siempre será el elemento más pequeño (a menos que el elemento más grande esté en el último índice, posible si no hubo rotación). 
Por eso,

Número de rotaciones (k) = índice del elemento más pequeño (k) en la array

A continuación se muestra la implementación del enfoque anterior:

// Java Program to find the
// count of rotations
public class GFG {
  
    // Function to return the count of
    // rotations
    public static int countRotation(int[] arr,
                                    int n)
    {
        for (int i = 1; i < n; i++) {
            // Find the smallest element
            if (arr[i] < arr[i - 1]) {
                // Return its index
                return i;
            }
        }
        // If array is not
        // rotated at all
        return 0;
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr1 = { 4, 5, 1, 2, 3 };
  
        System.out.println(
            countRotation(
                arr1,
                arr1.length));
    }
}

2

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)

Enfoque eficiente: 
para optimizar el enfoque anterior, utilizaremos la búsqueda binaria . Podemos notar que, después de ordenar y rotar, la array dada se divide en dos mitades con elementos no decrecientes, que es el único requisito previo para la búsqueda binaria. Realice una búsqueda binaria recursiva en la array para encontrar el índice del elemento más pequeño.

A continuación se muestra la implementación del enfoque anterior:

// Java Program to implement 
// the above approach 
  
public class GFG { 
  
    // Function to return the 
    // count of rotations 
    public static int countRotation(int[] arr, 
                                    int low, 
                                    int high) 
    { 
        // If array is not rotated 
        if (low > high) { 
            return 0; 
        } 
  
        int mid = low + (high - low) / 2; 
  
        // Check if current element is 
        // greater than the next 
        // element 
  
        if (mid < high 
            && arr[mid] > arr[mid + 1]) { 
            // the next element is 
            // the smallest 
            return mid + 1; 
        } 
  
        // Check if current element is 
        // smaller than it's previous 
        // element 
        if (mid > low 
            && arr[mid] < arr[mid - 1]) { 
            // Current element is 
            // the smallest 
            return mid; 
        } 
  
        // Check if current element is 
        // greater than lower bound 
  
        if (arr[mid] > arr[low]) { 
            // The sequence is increasing 
            // so far 
            // Search for smallest 
            // element on the right 
            // subarray 
            return countRotation(arr, 
                                mid + 1, 
                                high); 
        } 
  
        if (arr[mid] < arr[high]) { 
            // Smallest element lies on the 
            // left subarray 
            return countRotation(arr, 
                                low, 
                                mid - 1); 
        } 
  
        else { 
            // Search for the smallest 
            // element on both subarrays 
            int rightIndex = countRotation(arr, 
                                        mid + 1, 
                                        high); 
            int leftIndex = countRotation(arr, 
                                        low, 
                                        mid - 1); 
  
            if (rightIndex == 0) { 
                return leftIndex; 
            } 
  
            return rightIndex; 
        } 
    } 
  
    // Driver Program 
    public static void main(String[] args) 
    { 
        int[] arr1 = { 4, 5, 1, 2, 3 }; 
  
        System.out.println( 
            countRotation( 
                arr1, 
                0, arr1.length 
                    - 1)); 
    } 
} 

2

Complejidad de tiempo: O(N) 
La complejidad será O(logN) para una array sin duplicados. Pero si la array contiene duplicados, llamará recursivamente a la búsqueda de ambas mitades. Entonces, la complejidad del peor de los casos será O (N).

Espacio auxiliar: O(N) 
En el peor de los casos, la pila de llamadas recursivas tendrá N/2 llamadas recursivas a la vez.
 

Consulte el artículo completo sobre el recuento de rotaciones necesarias para generar una array ordenada para obtener más detalles.