class Solution {
public:
bool isIdealPermutation(vector<int>& nums) {
}
};
775. 全局倒置与局部倒置
给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。
全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
0 <= i < j < nnums[i] > nums[j]局部倒置 的数目等于满足下述条件的下标 i 的数目：
0 <= i < n - 1nums[i] > nums[i + 1]当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,0,2] 输出：true 解释：有 1 个全局倒置，和 1 个局部倒置。
示例 2：
输入：nums = [1,2,0] 输出：false 解释：有 2 个全局倒置，和 1 个局部倒置。
提示：
n == nums.length1 <= n <= 50000 <= nums[i] < nnums 中的所有整数 互不相同nums 是范围 [0, n - 1] 内所有数字组成的一个排列原站题解
golang 解法, 执行用时: 100 ms, 内存消耗: 8.9 MB, 提交时间: 2022-11-16 10:25:44
func isIdealPermutation(nums []int) bool {
for i, x := range nums {
if abs(x-i) > 1 {
return false
}
}
return true
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
python3 解法, 执行用时: 68 ms, 内存消耗: 25.1 MB, 提交时间: 2022-11-16 10:25:20
class Solution:
def isIdealPermutation(self, nums: List[int]) -> bool:
return all(abs(x - i) <= 1 for i, x in enumerate(nums))
golang 解法, 执行用时: 116 ms, 内存消耗: 8.9 MB, 提交时间: 2022-11-16 10:23:26
func isIdealPermutation(nums []int) bool {
n := len(nums)
minSuf := nums[n-1]
for i := n - 2; i > 0; i-- {
if nums[i-1] > minSuf {
return false
}
minSuf = min(minSuf, nums[i])
}
return true
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
python3 解法, 执行用时: 168 ms, 内存消耗: 25.1 MB, 提交时间: 2022-11-16 10:23:01
'''
一个局部倒置一定是一个全局倒置，因此要判断数组中局部倒置的数量是否与全局倒置的数量相等，
只需要检查有没有非局部倒置就可以了。这里的非局部倒置指的是 nums[i] > nums[j]，其中 i < j - 1。
'''
class Solution:
def isIdealPermutation(self, nums: List[int]) -> bool:
min_suf = nums[-1]
for i in range(len(nums) - 2, 0, -1):
if nums[i - 1] > min_suf:
return False
min_suf = min(min_suf, nums[i])
return True