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:
C++
// C++ program to find the
// count of rotations
#include <bits/stdc++.h>
using namespace std;
// Function to return the count
// of rotations
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
int main()
{
int arr1[] = { 4, 5, 1, 2, 3 };
int n = sizeof(arr1) / sizeof(int);
cout << countRotation(arr1, n);
}
// This code is contributed by jrishabh99
Java
// 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));
}
}
Python3
# Python3 program to find the # count of rotations # Function to return the count # of rotations def countRotation(arr, n): for i in range (1, n): # 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 if __name__ == "__main__": arr1 = [ 4, 5, 1, 2, 3 ] n = len(arr1) print(countRotation(arr1, n)) # This code is contributed by chitranayal
C#
// C# program to find the count of rotations
using System;
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 };
Console.WriteLine(countRotation(arr1,
arr1.Length));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program to find the
// count of rotations
// Function to return the count of
// rotations
function countRotation(arr, n)
{
for(let 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
let arr1 = [ 4, 5, 1, 2, 3 ];
document.write(countRotation(
arr1, arr1.length));
// This code is contributed by sanjoy_62
</script>
Producción:
2
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.
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:
C++
// C++ program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// count of rotations
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 code
int main()
{
int arr1[] = { 4, 5, 1, 2, 3 };
int N = sizeof(arr1) / sizeof(arr1[0]);
cout << countRotation(arr1, 0, N - 1);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// 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));
}
}
Python3
# Python3 program to implement the # above approach # Function to return the # count of rotations def countRotation(arr, low, high): # If array is not rotated if (low > high): return 0 mid = low + (high - low) // 2 # Check if current element is # greater than the next # element if (mid < high and 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 and 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 rightIndex = countRotation(arr, mid + 1, high) leftIndex = countRotation(arr, low, mid - 1) if (rightIndex == 0): return leftIndex return rightIndex # Driver code if __name__ == '__main__': arr1 = [ 4, 5, 1, 2, 3 ] N = len(arr1) print(countRotation(arr1, 0, N - 1)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
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 code
public static void Main(String[] args)
{
int[] arr1 = { 4, 5, 1, 2, 3 };
Console.WriteLine(countRotation(arr1, 0,
arr1.Length - 1));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to return the
// count of rotations
function countRotation(arr,low,high)
{
// If array is not rotated
if (low > high) {
return 0;
}
let mid = low + Math.floor((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
let rightIndex = countRotation(arr,
mid + 1,
high);
let leftIndex = countRotation(arr,
low,
mid - 1);
if (rightIndex == 0) {
return leftIndex;
}
return rightIndex;
}
}
// Driver Program
let arr1=[4, 5, 1, 2, 3 ];
document.write(
countRotation(
arr1,
0, arr1.length
- 1));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
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.