C++程序 计算旋转次数以使给定数组按非递增顺序排序

给定一个由 N 个整数组成的数组 arr[] ，任务是通过最小数量的逆时针旋转将数组按非递增顺序排序。如果不能对数组进行排序，则打印 “-1” 。否则，打印旋转的计数。

示例：

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

输出： 2

说明： 需要两次逆时针旋转才能将数组按降序排序，即{5, 4, 3, 2, 1}

输入： arr[] = {2, 3, 1}

输出： -1

方法： 想法是遍历给定的数组 arr[] 并计算满足 **arr[i + 1] > arr[i] ** 的索引数。按照以下步骤解决问题：

• 将 **arr[i + 1] > arr[i] ** 的数量计数，并将 **arr[i+1] > arr[i] ** 时的索引存储在变量中。
• 如果 计数 的值为 N – 1 ，则数组按非递减顺序排序。所需步骤正好为 (N – 1) 。
• 如果 计数 的值为 0 ，则数组已经按非递增顺序排序。
• 如果 计数 的值为 1 且 arr[0] ≤ arr[N – 1] ，则所需的旋转次数等于 (index + 1) ，通过对该索引之前的所有数字执行移动来实现。还要检查 arr[0] ≤ arr[N – 1] ，以确保序列是非递增的。
• 否则，不能将数组按非递增顺序排序。

下面是上述方法的实现：

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to count minimum anti-
// clockwise rotations required to
// sort the array in non-increasing order
void minMovesToSort(int arr[], int N)
{
    // Stores count of arr[i + 1] > arr[i]
    int count = 0;
  
    // Store last index of arr[i+1] > arr[i]
    int index;
  
    // Traverse the given array
    for (int i = 0; i < N - 1; i++) {
  
        // If the adjacent elements are
        // in increasing order
        if (arr[i] < arr[i + 1]) {
  
            // Increment count
            count++;
  
            // Update index
            index = i;
        }
    }
  
    // Print the result according
    // to the following conditions
    if (count == 0) {
        cout << "0";
    }
    else if (count == N - 1) {
        cout << N - 1;
    }
    else if (count == 1
             && arr[0] <= arr[N - 1]) {
        cout << index + 1;
    }
  
    // Otherwise, it is not
    // possible to sort the array
    else {
        cout << "-1";
    }
}
  
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 1, 5, 4, 2 };
    int N = sizeof(arr)
            / sizeof(arr[0]);
  
    // Function Call
    minMovesToSort(arr, N);
  
    return 0;
}  

输出:

2

时间复杂度： O(N)

辅助空间： O(1)