#Problem

#⭐️⭐️⭐️

说有[0, N - 1]个distinct的数在一个数组里位置被打乱了. Global inversions就是对于任意i, j, 满足i < j && A[i] > A[j]. Local inversions就是对于任意i, A[i] > A[i + 1].

问Global inversions的数量和local inversions的数量是否一样.

#Solution

global的数量如果和local的数量一样, 那么所有global其实也就是Local. 那么举几个例子就会发现规律:

1,2,3,4,5 => true
2,1,4,3,5 => true
4,3,2,1,5 => false
1,3,2,5,4 => true

所以对于每个A[i]来说, 它只可能出现在3个地方, i - 1, i 或者 i + 1. 因此只要遍历一遍看每一个A[i]是否满足条件即可.

#Code

#Java
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean isIdealPermutation(int[] A) {
for (int i = 0; i < A.length; i++) {
if (Math.abs(A[i] - i) > 1) {
return false;
}
}
return true;
}
}

Comments