775. Global and Local Inversions
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
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 |
|
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 |
|
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 |
|