模拟
理解题，全局倒置就是不相邻的逆序对，局部倒置就是相邻的逆序对。提示中给出， 0 < = n u m s [ i ] < n 0 <= nums[i] < n 0<=nums[i]<n ，其中 n = = n u m s . l e n g t h n == nums.length n==nums.length , n u m s nums nums 中的所有整数 互不相同，可知 n u m s nums nums 中包含 0 0 0 到 n − 1 n-1 n−1 所有数。
分情况理解:
- 所有数按顺序 从 0 0 0 到 n − 1 n-1 n−1 排列，顺序数组，符合条件， r e t u r n t r u e return~true return true。
- 相邻的数颠倒顺序，如 0 1 2 0~1~2 0 1 2 变成 1 0 2 1~0~2 1 0 2 ，发现逆序对 < 1 , 0 > <1,0> <1,0>前一个数 1 1 1 减下标相差 1 1 1 ， 后一个数 0 0 0 减下标相差 − 1 -1 −1 。数和下标相差 1 1 1 或 − 1 -1 −1 ，是局部倒置的条件，符合 t r u e true true 的要求。
- 同理，一个数和自己下标相差大于 1 1 1 ，这就是不相邻的逆序对(全局倒置)， r e t u r n f a l s e return~false return false。
本题之所以这么简单，是因为题目限制诸多。如果没有 n u m s nums nums 是范围 [ 0 , n − 1 ] [0, n - 1] [0,n−1] 内所有数字组成的一个排列，这个限制，那么博主一时之间只能想到暴力循环了~
代码展示
class Solution {
public:bool isIdealPermutation(vector<int>& nums) {for(int i = 0;i<nums.size();i++)if(nums[i]!= i &&i-1!=nums[i]&&i+1!=nums[i]) return false;return true;}
};
合并同类项
class Solution {
public:bool isIdealPermutation(vector<int>& nums) {for(int i = 0;i<nums.size();i++)if(abs(nums[i]-i)>1) return false;return true;}
};
博主致语
理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。
AC
复杂度分析
- 时间复杂度: O ( n ) O(n) O(n)， n n n 是 n u m s nums nums 的长度。 ，一次遍历 n u m s nums nums 的时间复杂度是 O ( n ) O(n) O(n) 。
- 空间复杂度: O ( 1 ) O(1) O(1)，除若干变量使用的常量级空间，没有使用额外线性空间。
