↓Skip to main content
  1. Posts/

LeetCode-775 全局倒置与局部倒置

·1 min·
Table of Contents

LeetCode-775 全局倒置与局部倒置 #

Solution 1 #

全局倒置一定包含局部倒置, 所以要求排列只包含局部倒置. 考虑一个 $n = 4$ 的简单情况: $1, 0, 3, 2$ 为 true , 而 $1, 2, 0, 3$ 为 false . 如果只包含局部倒置, 那么每个元素要么是在原位, 要么与相邻元素进行了交换. 我们检查是否存在 $\vert nums[i] - i > 1\vert$ 即可. 代码如下:

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;
    }
};