题目描述
leetcode 中等题
给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。
全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
- 0 <= i < j < n
- nums[i] > nums[j]
局部倒置 的数目等于满足下述条件的下标 i 的数目：
- 0 <= i < n - 1
- nums[i] > nums[i + 1]
当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。
示例1：
1
2
3
| 输入：nums = [1,0,2]
输出：true
解释：有 1 个全局倒置，和 1 个局部倒置。
|
示例2：
1
2
3
| 输入：nums = [1,2,0]
输出：false
解释：有 2 个全局倒置，和 1 个局部倒置。
|
提示：
1
2
3
4
5
| n == nums.length
1 <= n <= 10^5
0 <= nums[i] < n
nums 中的所有整数 互不相同
nums 是范围 [0, n - 1] 内所有数字组成的一个排列
|
遍历
这道题最容易且方便的做法是，逆序遍历且维护一个 $[i + 2, n]$ 的最小值，如果当前元素大于该最小值返回 $false$ ，如果顺利遍历结束返回 $true$ 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean isIdealPermutation(int[] nums) {
int n = nums.length;
int min = nums[n - 1];
for(int i = n - 3; i >= 0; i--){
if(nums[i] > min){
return false;
}
min = Math.min(min, nums[i + 1]);
}
return true;
}
}
|
树状数组
对于求 逆序对 更通用的做法是使用 树状数组。
由于树状数组的索引位置 $0$ 一般不会存储元素，因为 $lowbit(0) = 0$，会导致 $query$ 和 $update$ 的循环条件都要进行特判，然而题目数据范围为 $0 <= nums[i] < n$，会取到 $0$。
一种方法是构造一个原数组元素与排名的映射（排名从 $1$ 开始），使得原数组离散化，这样既不会取到 $0$ 的索引，也能压缩数字区间（虽然本题数据为排列，所以起到没有压缩作用）。
构建完映射之后只需要通过树状数组得到逆序对的总数量，再与“局部倒置”的数量比较即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution {
public boolean isIdealPermutation(int[] nums) {
int n = nums.length;
int[] sort = new int[n];
System.arraycopy(nums, 0, sort, 0, n);
Arrays.sort(sort);
Map<Integer, Integer> rank = new HashMap<>();
for(int i = 1; i < n + 1; i++){
rank.put(sort[i - 1], i);
}
FenwickTree t = new FenwickTree(rank.keySet().size() + 1);
int local = 0, global = 0;
for(int i = 0; i < n; i++){
int r = rank.get(nums[i]);
t.update(r, 1);
global += t.query(rank.keySet().size()) - t.query(r);
if(i != n - 1 && nums[i] > nums[i + 1]){
local += 1;
}
}
return local == global;
}
static class FenwickTree{
int[] c;
FenwickTree(int size){
c = new int[size];
}
void update(int index, int updateValue){
while(index < c.length){
c[index] += updateValue;
index += lowbit(index);
}
}
int query(int index){
int ans = 0;
while(index > 0){
ans += c[index];
index -= lowbit(index);
}
return ans;
}
private int lowbit(int x){
return x & -x;
}
}
}
|
另一种避免取到 $0$ 的方法是每次加入树状数组时把元素手动加上 $1$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean isIdealPermutation(int[] nums) {
int n = nums.length;
FenwickTree t = new FenwickTree(nums.length + 1);
int local = 0, global = 0;
for(int i = 0; i < n; i++){
int item = nums[i] + 1;
global += t.query(n) - t.query(item);
t.update(item, 1);
if(i != n - 1 && nums[i] > nums[i + 1]){
local += 1;
}
}
return local == global;
}
}
|