力扣(LeetCode)775. 全局倒置与局部倒置(C++)

模拟

理解题，全局倒置就是不相邻的逆序对，局部倒置就是相邻的逆序对。提示中给出，$0<=nums[i]<n$ ，其中 $n==nums.length$ , $nums$ 中的所有整数 互不相同，可知 $nums$ 中包含 $0$ 到 $n-1$ 所有数。
分情况理解:

1. 所有数按顺序 从 $0$ 到 $n-1$ 排列，顺序数组，符合条件， $returntrue$。
2. 相邻的数颠倒顺序，如 $012$ 变成 $102$ ，发现逆序对 $<1,0>$前一个数 $1$ 减下标相差 $1$ ， 后一个数 $0$ 减下标相差 $-1$ 。数和下标相差 $1$ 或 $-1$ ，是局部倒置的条件，符合 $true$ 的要求。
3. 同理，一个数和自己下标相差大于 $1$ ，这就是不相邻的逆序对(全局倒置)， $returnfalse$。

本题之所以这么简单，是因为题目限制诸多。如果没有 $nums$ 是范围 $[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;
    }
};
1
2
3
4
5
6
7
8

合并同类项

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;
    }
};
1
2
3
4
5
6
7
8

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(n)$， $n$ 是 $nums$ 的长度。 ，一次遍历$nums$ 的时间复杂度是 $O(n)$ 。
2. 空间复杂度: $O(1)$，除若干变量使用的常量级空间，没有使用额外线性空间。