·
Noir@Zh
题解-全局倒置和部分倒置-找数学规律
思路
- 根据题意可知全局倒置包含局部倒置，对于本题如果有 非局部倒置 的全局倒置，则返回false，不然就返回true
- 很容易相出用暴力去搜索自己2位之后的数组元素中是否有比自己小的，时间复杂度:$O(n^2)$
- 倒置是根据的是递增数组出现的，也就是说我们得到的数组实际上是对递增数组进行过几次置换的数组
- 根据定义可以知道局部倒置的实质就是将相邻的数组元素进行的交换，所以要做的就是与原数组进行比较
- 位置不变的跳过
- 位置变化的判断是否和原数组相邻位置的值相等，相等则跳过
- 不满足上述两个条件的就是全局置换，返回false
代码
class Solution {
public:
bool isIdealPermutation(vector<int>& nums) {
int n=nums.size()-1;
int i=0;
while (i<n){
if (nums[i]==i)
i++;
else if (nums[i]==i+1&&nums[i+1]==i)
i+=2;
else
return false;
}
return true;
}
};