算法1
找到连续的下降子数组并且记录位置将它翻转,将反转后的序列和1-n的排列比较
时间复杂度 o(n)
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
int a[1010];
int n;
int main()
{
int l = 0,r = 0;
cin >> n;
vector <int> st;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i + 1 <= n; i ++){
if(a[i] > a[i + 1]){//记录下降子数组的第一个位置
l = i;
break;
}
}
for(int i = 1; i + 1 <= n; i ++){
if(a[i] > a[i + 1]){//记录下降子数组的第二个位置
r = i + 1;
}
}
//用st记录翻转后的序列
for(int i = 1; i < l; i ++) st.push_back(a[i]);
for(int i = r; i >= l; i --) st.push_back(a[i]);
for(int i = r + 1; i <= n; i ++) st.push_back(a[i]);
for(int i = 0; i < n; i ++) if(st[i] != i + 1){//比较就行
cout << 0 << ' ' << 0;
return 0;
}
cout << l << " " << r;
return 0;
}