c++ - 确定数组是否可以排序旋转 3 个连续的数组元素？

Question

我有一个从 1 递增的自然数序列的排列作为一个数组。如何确定数组是否可以使用 3 个连续元素的旋转进行排序？

我已经实现了一种算法，基本上我将数组的索引与数组中该索引处的元素进行比较。如果它们不相等，那么我调用函数 choose_indices() ，它首先在数组中的正确位置找到要交换的元素，找到它后，选择 3 个连续的元素，包括要交换的数字并旋转它们。对大小为 n 的数组执行 n-1 次旋转后，数组就被排序了。如果可以使用 3 个连续元素旋转对数组进行排序，则此实现返回 true，但如果无法使用此方法对数组进行排序，则数组超时。

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
int n;
void rotate(vector<int> &arr,int end,int mid,int start)
{
    int temp=arr[start];
    arr[start]=arr[end];
    arr[end]=arr[mid];
    arr[mid]=temp;
}
void choose_indices(vector<int> &arr,int s,int q)
{
    for(int l=q;l<n;l++)
    {
        if(arr[l]==s)
        {
            if(l-q>=2)
            {
                rotate(arr,l,l-1,l-2);
                break;
            }
            else
            {
                rotate(arr,l+1,l,l-1);
                break;
            }
        }
    }
}
int main()
{
    vector<int> arr;
    int q,count=0;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>n;
        count=0;
        for(int i=0,p;i<n;i++)
        {
            cin>>p;
            arr.push_back(p);
        }
        for(int j=0,k=1;j<n && k<n; )
        {
            if(arr[j]!=k)
            {
                choose_indices(arr,k,j);
                if(arr[j]==k)
                {
                    j++;
                    k++;
                    count++;
                }
            }
            else
            {
                j++;
                k++;
                count++;
            }
        }
        if(count==n-1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
           cout<<"NO"<<endl;
        }
        arr.clear();
    }
}

示例输入: 1 2 3 5 4

对于这个输入，我的代码给出了运行时错误。 如何找到给定的数组是否无法使用 3 个连续元素的旋转进行排序？

Answer 1

旋转 3 个相邻元素将始终取消 2 个反转(如果存在)或引入 2 个反转。

考虑一下:

1 2 3 5 4

只有 1 个反转，无论您旋转多少次，您都无法在不引入其他反转的情况下取消该反转，因为您将始终旋转 3 个连续的元素。

因此，只需计算反转的次数，如果是奇数，则答案为NO，否则为YES。有一些有效的算法可以计算倒置的次数(如归并排序)。