c++ - 确定数组是否可以旋转 3 个连续的数组元素进行排序?
问题描述
我有一个从 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 个连续元素的旋转对给定的数组进行排序,我该如何查找?
解决方案
旋转 3 个相邻元素将始终取消 2 个反转(如果存在),否则将引入 2 个反转。
考虑一下:
1 2 3 5 4
只有 1 个反转,无论您旋转多少次,如果不引入其他反转,您永远无法取消该反转,因为您将始终旋转 3 个连续元素。
因此,只需计算反转的次数,如果它是奇数,则答案为NO,否则为YES。有有效的算法来计算反转的数量(如合并排序)。
推荐阅读
- javascript - JS 在 Firefox 中不起作用
- html - thymeleaf 上的条件运算符
- ruby-on-rails - 在本机反应中呈现 JSON 数据
- php - 选择喜欢但作为分隔符之间的整个字符串
- javascript - 在 puppeteer 中使用提示符
- amazon-web-services - 如何定义将接受任何给定值的 Lex 插槽类型(自定义/内置)?
- java - 如何使用 Java 代码创建 Kafka 分区
- db2 - DB2 select row isolation not working
- javascript - 内部错误 NodeJS
- macos - 如何检查应用程序是否是钥匙串条目 ACL 的一部分?