C++程序计算生成排序数组所需旋转的次数

给定一个 数组 arr[] ，任务是找到将给定数组转换为排序形式所需的旋转次数。
示例:

输入: arr[] = {4, 5, 1, 2, 3}

输出: 2

解释:

需要2次逆时针旋转后形成排序数组{1, 2, 3, 4, 5}。

输入: arr[] = {2, 1, 2, 2, 2}

输出: 1

解释:

需要1次逆时针旋转后形成排序数组{1, 2, 2, 2, 2}。

Naive Approach:

为了解决上述问题，我们首先观察到，如果数组中有 n 个元素，则排序后最大的元素位于第(n – 1)个位置。进行k次逆时针旋转后，最大元素将位于索引(k – 1)（从开始数的第k个元素）。另外一个需要注意的是，旋转后最大元素的下一个元素始终是最小元素（除非最大元素在最后一个索引上，如果没有旋转就可能出现）。
因此，

旋转次数(k) = 数组中最小元素的索引(k)

下面是实现上述方法的代码:

// 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```

输出:

时间复杂度: O(N)

辅助空间: O(1)

Efficient Approach:

为了优化上述方法，我们将使用二分查找。我们可以注意到，在排序并旋转后，给定的数组被分成两个具有非递减元素的部分，这是二分查找的唯一前提条件。在数组中执行递归二分查找以找到最小元素的索引。

下面是实现上述方法的代码:

// C++程序实现如上方法
#include <bits/stdc++.h>
using namespace std;

// 返回旋转次数的函数
int countRotation(int arr[], int low,
                                    int high)
{   

    // 如果数组没有旋转
    if (low > high)
    {   
        return 0;   
    }   

    int mid = low + (high - low) / 2;   

    // 检查当前元素是否大于下一个元素
    if (mid < high && arr[mid] > arr[mid + 1])
    {   

        // 下一个元素是最小的
        return mid + 1;   
    }   

    // 检查当前元素是否小于它的前一个元素
    if (mid > low && arr[mid] < arr[mid - 1])
    {   

        // 当前元素是最小的
        return mid;   
    }   

    // 检查当前元素是否大于下界
    if (arr[mid] > arr[low])   
    {

        // 序列迄今为止增加
        // 在右子阵列中搜索最小元素
        return countRotation(arr, mid + 1,
                                                high);  
    }   

    if (arr[mid] < arr[high])
    {   

        // 最小元素在左子阵列上
        return countRotation(arr, low,
                                                mid - 1);  
    }   
    else   
    {   

        // 在两个子阵列上搜索最小元素
        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;
}

// 该代码由divyeshrabadiya07贡献```

输出:

时间复杂度: O（N）

对于没有重复项的数组，复杂性将为O（logN）。但是，如果数组包含重复项，则它将递归地调用搜索来寻找两个半部分。因此，最坏情况下的复杂度将是O（N）。

辅助空间: O（N）
在最坏的情况下，递归调用堆栈将同时具有N / 2个递归调用。