0775-全局倒置与局部倒置

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你一个长度为 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：

**输入：** nums = [1,0,2]
**输出：** true
**解释：** 有 1 个全局倒置，和 1 个局部倒置。

示例 2：

**输入：** nums = [1,2,0]
**输出：** false
**解释：** 有 2 个全局倒置，和 1 个局部倒置。

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 0 <= nums[i] < n
  • nums 中的所有整数 互不相同
  • nums 是范围 [0, n - 1] 内所有数字组成的一个排列

方法一：维护后缀最小值

思路与算法

一个局部倒置一定是一个全局倒置，因此要判断数组中局部倒置的数量是否与全局倒置的数量相等，只需要检查有没有非局部倒置就可以了。这里的非局部倒置指的是 nums}[i] \gt \textit{nums}[j]，其中 i < j - 1。

朴素的判断方法需要两层循环，设 n 是 nums 的长度，那么该方法的时间复杂度为 O(n^2)，无法通过。

进一步的，对于每一个 nums}[i] 判断是否存在一个 j~(j \gt i + 1) 使得 nums}[i] \gt nums[j] 即可。这和检查 nums}[i] \gt \min(\textit{nums}[i+2],\dots,\textit{nums}[n-1]) 是否成立是一致的。因此我们维护一个变量 minSuffix} = \min(\textit{nums}[i+2],\dots,\textit{nums}[n-1])，倒序遍历 [0, n-3] 中的每个 i, 如有一个 i 使得 nums}[i] \gt \textit{minSuffix 成立，返回 false，若结束遍历都没有返回 false，则返回 true。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
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
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        int n = nums.size(), minSuff = nums[n - 1];
        for (int i = n - 3; i >= 0; i--) {
            if (nums[i] > minSuff) {
                return false;
            }
            minSuff = min(minSuff, nums[i + 1]);
        }
        return true;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length, minSuff = nums[n - 1];
        for (int i = n - 3; i >= 0; i--) {
            if (nums[i] > minSuff) {
                return false;
            }
            minSuff = Math.min(minSuff, nums[i + 1]);
        }
        return true;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public bool IsIdealPermutation(int[] nums) {
        int n = nums.Length, minSuff = nums[n - 1];
        for (int i = n - 3; i >= 0; i--) {
            if (nums[i] > minSuff) {
                return false;
            }
            minSuff = Math.Min(minSuff, nums[i + 1]);
        }
        return true;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
var isIdealPermutation = function(nums) {
    let n = nums.length, minSuff = nums[n - 1];
    for (let i = n - 3; i >= 0; i--) {
        if (nums[i] > minSuff) {
            return false;
        }
        minSuff = Math.min(minSuff, nums[i + 1]);
    }
    return true;
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
#define MIN(a, b) ((a) < (b) ? (a) : (b))

bool isIdealPermutation(int* nums, int numsSize) {
    int minSuff = nums[numsSize - 1];
    for (int i = numsSize - 3; i >= 0; i--) {
        if (nums[i] > minSuff) {
            return false;
        }
        minSuff = MIN(minSuff, nums[i + 1]);
    }
    return true;
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是 nums 的长度。

  • 空间复杂度：O(1)，只使用到常数个变量空间。

方法二：归纳证明

思路与算法

nums 是一个由 0\sim n-1 组成的排列，设不存在非局部倒置的排列为「理想排列」。由于非局部倒置表示存在一个 j > i + 1 使得 nums}[i] > \textit{nums}[j] 成立，所以对于最小的元素 0 来说，它的下标不能够大于等于 2。所以有：

  1. 若 nums}[0] = 0，那么问题转换为 [1, n - 1] 区间的一个子问题。
  2. 若 nums}[1] = 0，那么 nums}[0] 只能为 1，因为如果是大于 1 的任何元素，都将会与后面的 1 构成非局部倒置。此时，问题转换为了 [2, n - 1] 区间的一个子问题。

根据上述讨论，不难归纳出「理想排列」的充分必要条件为对于每个元素 nums}[i] 都满足 \big| \textit{nums}[i] - i \big| \le 1。

代码

[sol2-Python3]
1
2
3
class Solution:
    def isIdealPermutation(self, nums: List[int]) -> bool:
        return all(abs(x - i) <= 1 for i, x in enumerate(nums))
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public bool IsIdealPermutation(int[] nums) {
        for (int i = 0; i < nums.Length; i++) {
            if (Math.Abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
var isIdealPermutation = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        if (Math.abs(nums[i] - i) > 1) {
            return false;
        }
    }
    return true;
};
[sol2-C]
1
2
3
4
5
6
7
8
bool isIdealPermutation(int* nums, int numsSize){
    for (int i = 0; i < numsSize; i++) {
        if (abs(nums[i] - i) > 1) {
            return false;
        }
    }
    return true;
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是 nums 的长度。

  • 空间复杂度：O(1)，只使用到常数个变量空间。

 Comments
On this page
0775-全局倒置与局部倒置