C++程序将给定数组旋转以使其成为非递减数组

给定大小为 N （包括重复项）的数组 arr [] ，任务是检查是否可以通过旋转将给定数组转换为非递减数组。如果不可能，那么打印“ No ”。否则，打印“ Yes “。

示例：

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

输出： Yes

解释： 右旋转2次后，数组 arr [] 修改为 {1, 2, 3, 4, 5}

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

输出： No

方法： 这种想法基于这样一个事实，即通过旋转给定的数组可以得到最大的 N 种不同的数组，并检查每个单独旋转的数组是否为非递减或不是非递减数组。按照以下步骤解决问题：

初始化一个向量，如 v，并将原始数组的所有元素复制到其中。
对矢量 v 进行排序。
遍历原始数组并执行以下步骤：
- 每次迭代旋转1个。
- 如果数组变成向量 v ，打印“ Yes ”。否则，打印“ No ”。

以下是上述方法的实现：

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to check if a
// non-decreasing array can be obtained
// by rotating the original array
void rotateArray(vector& arr, int N)
{
    // Stores copy of original array
    vector v = arr;
  
    // Sort the given vector
    sort(v.begin(), v.end());
  
    // Traverse the array
    for (int i = 1; i <= N; ++i) {
  
        // Rotate the array by 1
        rotate(arr.begin(),
               arr.begin() + 1, arr.end());
  
        // If array is sorted
        if (arr == v) {
  
            cout << "YES" << endl;
            return;
        }
    }
  
    // If it is not possible to
    // sort the array
    cout << "NO" << endl;
}
  
// Driver Code
int main()
{
    // Given array
    vector arr = { 3, 4, 5, 1, 2 };
  
    // Size of the array
    int N = arr.size();
  
    // Function call to check if it is possible
    // to make array non-decreasing by rotating
    rotateArray(arr, N);
}

输出