Problem
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:
1 | Input: nums = [1,0,2] |
Example 2:
1 | Input: nums = [1,2,0] |
Constraints:
n == nums.length
1 <= n <= 5000
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]
.
Analysis
题目给出两个概念:局部倒序和全局倒序。局部倒序指的是相邻的的两个数字,下标较大的数值比较小;全局倒序指的是数组中任意的两个数字,下标较大的数值比较小。这两者的区别就在于,比较的这两个数字是否相邻。因为题目只需要判断局部倒序的数量是否等于全局倒序的数量,所以可以转化为,能否找到一个倒序,是全局倒序而不是局部倒序。如果能找到,则return false;否则return true。
我们先来看一个是全局倒序而不是局部倒序的例子,最简单的就是题目给出的Example2。[1, 2, 0]
中,1在0的前面(而且不相邻),但是1比0要大。所以我们就是要找得到像这种结构,就说明存在全局倒序,而又不是局部倒序。接下来就看怎么去找这种结构。
暴力循环的方法这里就不提了,这里介绍一种比较巧妙的做法。正常来说,如果下标和值对应的话,下标为i
的位置的值应该是i + 1
,假设某个位置i
的值不是i + 1
,而是i + 3
(因为如果是i + 2
的话,就是局部倒序,这里要构造出全局倒序),那么说明i + 2
的位置的值是i + 1
。此时,位置i
的值就是i + 2
,所以下标和值之间差的绝对值大于1。我们就是要利用这个性质去寻找是否存在全局倒序。
Solution
无
Code
1 | class Solution { |
Summary
这道题目重在分析,代码方面没有很复杂的逻辑和技术难点。这道题目的分享到这里,感谢你的支持!