全局倒置与局部倒置【LC775】
给你一个长度为 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
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.
树状数组看的脑壳疼…
暴力
- 思路：暴力… 超时
class Solution { public boolean isIdealPermutation(int[] nums) { int global = 0; int local = 0; int len = nums.length; for (int i = 0; i < len - 1; i++){ if (nums[i] > nums[i+1]){ local++; } for (int j = i + 1; j < len; j++){ if (nums[i] > nums[j]){ global++; } } } return global == local; } }
- 复杂度
。时间复杂度：O ( n 2 )
。空间复杂度：O ( 1 )
数学
- 思路：局部倒置一定是全局倒置，如果除了局部倒置时，还存在其他倒置，那么返回false
- 实现：记录前缀数组nums[0,i-2]的最大值，如果nums[i]<max，那么返回false
- 代码
class Solution { public boolean isIdealPermutation(int[] nums) { int max = 0; for (int i = 2; i < nums.length; i++){ if (nums[i] < max){ return false; } max = Math.max(max,nums[i-1]); } return true; } }
- 复杂度
。时间复杂度：O ( n )
。空间复杂度：O ( 1 )
树状数组
- 思路：对于nums[i]，其左边比它大的nums[j]的个数，即为以nums[i]为右端点的全局倒置的数量
- 实现：使用树状数组统计左边比nums[i]大的个数
。tr[i]代表当前已经遍历到的数组数值小于等于i的总数量
- 代码
class Solution { int n; int[] tr; int lowbit(int x) { return x & -x; } void add(int x) { for (int i = x; i <= n; i += lowbit(i)) tr[i]++; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } public boolean isIdealPermutation(int[] nums) { n = nums.length; tr = new int[n + 10]; add(nums[0] + 1);// 更新tr数组下标0-nums[0]+1 使其数量+1 int a = 0, b = 0; for (int i = 1; i < n; i++) { a += query(n) - query(nums[i] + 1); // query(n)为当前加入的数的总数，即等于i // query(nums[i] + 1) 为nums[0,i-1]小于等于nums[i] + 1的数量 // 相减即为以nums[i]为右端点的逆序对的数量【全局倒置】 b += nums[i] < nums[i - 1] ? 1 : 0; add(nums[i] + 1); } return a == b; } } 作者：宫水三叶 链接：https://leetcode.cn/problems/global-and-local-inversions/solutions/1973365/by-ac_oier-jc7a/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度
。时间复杂度：O ( n l o g n )
。空间复杂度：O ( n )
