775. Global and Local Inversions

local 是global 的一個subset, 當A[i] > A[i + 1], global 的j == i + 1

所以一旦發現一個local, 必存在一個global, 反之當global的j != i+1

即可回傳false

但 O(n²)的時間複雜度太長, 要怎麼簡化？

class Solution {
public:
  bool isIdealPermutation(vector<int> &A) {
    int n = A.size();
    for(int i = 0; i < n - 1;i++){
      for(int j = i + 1; j < n;j++){
        if(A[j] < A[i]){
          if(j != i + 1){
            return false;
          }
        }
      }
    }
    return true;
  }
};

我們觀察一下規律

0,1,2,3,4
要符合題議的話
會是
1,0,3,2,4
可以看到會是0,1 swap, 2,3swap,

也就是說, 當index跟當前的值差>1, 代表放錯位置了

class Solution {
public:
  bool isIdealPermutation(vector<int> &A) {
    int n = A.size();
    for(int i = 0; i < n;i++){
        if(abs(i - A[i]) > 1){
            return false;
        }
    }
      return true;
  }
};

好難喔XD