Description
You are given an integer array nums
of length n
which represents a permutation of all the integers in the range [0, n - 1]
.
The number of global inversions is the number of the different pairs (i, j)
where:
0 <= i < j < n
nums[i] > nums[j]
The number of local inversions is the number of indices i
where:
0 <= i < n - 1
nums[i] > nums[i + 1]
Return true
if the number of global inversions is equal to the number of local inversions.
Example 1:
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.
Example 2:
Input: nums = [1,2,0]
Output: false
Explanation: There are 2 global inversions and 1 local inversion.
Constraints:
n == nums.length
1 <= n <= 105
0 <= nums[i] < n
- All the integers of
nums
are unique.
nums
is a permutation of all the numbers in the range [0, n - 1]
.
Solutions
Solution 1
Solution 2
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 | class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x):
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def isIdealPermutation(self, nums: List[int]) -> bool:
n = len(nums)
tree = BinaryIndexedTree(n)
cnt = 0
for i, v in enumerate(nums):
cnt += i < n - 1 and v > nums[i + 1]
cnt -= i - tree.query(v)
if cnt < 0:
return False
tree.update(v + 1, 1)
return True
|
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 | class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
public int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= x & -x;
}
return s;
}
}
class Solution {
public boolean isIdealPermutation(int[] nums) {
int n = nums.length;
BinaryIndexedTree tree = new BinaryIndexedTree(n);
int cnt = 0;
for (int i = 0; i < n && cnt >= 0; ++i) {
cnt += (i < n - 1 && nums[i] > nums[i + 1] ? 1 : 0);
cnt -= (i - tree.query(nums[i]));
tree.update(nums[i] + 1, 1);
}
return cnt == 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 | class BinaryIndexedTree {
public:
BinaryIndexedTree(int _n)
: n(_n)
, c(_n + 1) {}
void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
int query(int x) {
int s = 0;
while (x) {
s += c[x];
x -= x & -x;
}
return s;
}
private:
int n;
vector<int> c;
};
class Solution {
public:
bool isIdealPermutation(vector<int>& nums) {
int n = nums.size();
BinaryIndexedTree tree(n);
long cnt = 0;
for (int i = 0; i < n && ~cnt; ++i) {
cnt += (i < n - 1 && nums[i] > nums[i + 1]);
cnt -= (i - tree.query(nums[i]));
tree.update(nums[i] + 1, 1);
}
return cnt == 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 | func isIdealPermutation(nums []int) bool {
n := len(nums)
tree := newBinaryIndexedTree(n)
cnt := 0
for i, v := range nums {
if i < n-1 && v > nums[i+1] {
cnt++
}
cnt -= (i - tree.query(v))
if cnt < 0 {
break
}
tree.update(v+1, 1)
}
return cnt == 0
}
type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) BinaryIndexedTree {
c := make([]int, n+1)
return BinaryIndexedTree{n, c}
}
func (this BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += x & -x
}
}
func (this BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= x & -x
}
return s
}
|