## 题目描述：

LeetCode 775. Global and Local Inversions

We have some permutation `A` of `[0, 1, ..., N - 1]`, where `N` is the length of `A`.

The number of (global) inversions is the number of `i < j` with `0 <= i < j < N` and `A[i] > A[j]`.

The number of local inversions is the number of `i` with `0 <= i < N` and `A[i] > A[i+1]`.

Return `true` if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

```Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.
```

Example 2:

```Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.
```

Note:

• `A` will be a permutation of `[0, 1, ..., A.length - 1]`.
• `A` will have length in range `[1, 5000]`.
• The time limit for this problem has been reduced.

## Java代码：

``````class Solution {
public boolean isIdealPermutation(int[] A) {
return localInversion(A) == globalInversion(A);
}
public int localInversion(int[] A) {
int sum = 0;
for (int i = 0; i < A.length - 1; i++) {
if (A[i] > A[i + 1]) sum++;
}
return sum;
}
public int globalInversion(int[] nums) {
FenwickTree ft = new FenwickTree(nums.length);
int[] idexes = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
idexes[nums[i]] = i + 1;
}
int ans = 0;
for (int i = nums.length - 1; i >= 0; i--) {
ans += ft.sum(idexes[i] - 1);
}
return ans;
}
class FenwickTree {
int n;
int sums[];
public FenwickTree(int n) {
this.n = n;
sums = new int[n + 1];
}
void add(int x, int val) {
while (x <= this.n) {
sums[x] += val;
x += lowbit(x);
}
}
int lowbit(int x) {
return x & -x;
}
int sum(int x) {
int res = 0;
while (x > 0) {
res += sums[x];
x -= lowbit(x);
}
return res;
}
}

}
``````

Pingbacks已关闭。