第26天
今天的题目是Global and Local Inversions:
看上去挺复杂的题目,但是我们可以从题目中知道,输入的数组是一个 [0,1,...,N-1]
的一个排列,所以A中的元素是有限定的,
多举几个例子就可以发现如果一个排列要满足 local inversion
和 global inversion
个数相同的话,必须满足:
A[i] == i
A[i] == i+1 && A[i+1] == i
所以我们就可以写出这段代码:
1bool isIdealPermutation(vector<int>& A) {2 int minLimit = INT_MIN;3 for(int i = 0, size = A.size() - 1; i < size; i++) {4 if (A[i] == i) ;5 else if (A[i] == i + 1 && A[i+1] == i) {6 i++;7 } else return false;8 }9 return true;10}