LeetCode_数学归纳_中等_775.全局倒置与局部倒置

灰太狼 2023-10-07 21:12 46阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个长度为 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\] 内所有数字组成的一个排列

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/global-and-local-inversions

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法比较容易想到，即使用两层 for 循环来**统计全局倒置的数目和局部倒置的数目**，遍历结束后，如果两者相等则返回 true，否则返回 false。但是该方法的时间复杂度为 O(n2)，在 LeetCode 中提交会出现“超出时间限制”的提示！

另外还有一种类似的思路（不过也超时了）：由题意可知，**一个局部倒置一定是一个全局倒置，因此如果数组 nums 中存在某个全局倒置，但又不是局部倒置，那么说明两者的数量一定不想等**，此时直接返回 false 即可。

（2）维护最小后缀值  
思路参考[本题官方题解][Link 1]。

① 承接（1）中的第二种思路，要想判断某个倒置为全局倒置，但又不是局部倒置，即需判断 nums\[i\] > nums\[j\]，i + 1 < j，这与判断 nums\[i\] > min(nums\[i + 2\], nums\[i + 3\], …, nums\[nums.length - 1\]) 一致。

**② 所以只需维护一个变量 minSuffix，使其记录数组 nums 的最小后缀值即可，其初始值为 nums\[nums.length - 1\]。**

③ 然后再倒序遍历 nums\[0…nums.length - 3\] 中的每一个 i，如果存在某个 i，使得 nums\[i\] > minSuffix 成立，则直接返回 false。如果遍历结束后仍未找到这样的 i，那么返回 true 即可。

（3）数学归纳证明  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public boolean isIdealPermutation(int[] nums) {
        
        	// global 记录全局倒置的数目
            int global = 0;
            // local 记录局部倒置的数目
            int local = 0;
            int length = nums.length;
            //暴力穷举法来统计 global 和 local
            for (int i = 0; i < length; i++) {
        
                for (int j = i + 1; j < length; j++) {
        
                    if (nums[i] > nums[j]) {
        
                        if (j == i + 1) {
        
                            local++;
                        }
                        global++;
                    }
                }
            }
            return global == local;
        }
    }
    
    //另一种类似的思路
    class Solution {
        
        public boolean isIdealPermutation(int[] nums) {
        
            int notLocal = 0;
            int length = nums.length;
            for (int i = 0; i < length; i++) {
        
                for (int j = i + 2; j < length; j++) {
        
                	//如果 nums[i] > nums[j]，那么则说明存在某个全局倒置，但又不是局部倒置
                    if (nums[i] > nums[j]) {
        
                        return false;
                    }
                }
            }
            return true;
        }
    }

//思路2————维护最小后缀值
    class Solution {
        
        public boolean isIdealPermutation(int[] nums) {
        
            int length = nums.length;
            // minSuffix 记录数组 nums 的后缀最小值，初始值为 nums[length - 1]
            int minSuffix = nums[length - 1];
            for (int i = length - 3; i >= 0; i--) {
        
            	//如果 nums[i] > minSuffix，那么则说明存在某个全局倒置，但又不是局部倒置
                if (nums[i] > minSuffix) {
        
                    return false;
                }
                //更新 minSuffix
                minSuffix = Math.min(minSuffix, nums[i + 1]);
            }
            return true;
        }
    }

//思路3————数学归纳证明
    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;
        }
    }

[Link 1]: https://leetcode.cn/problems/global-and-local-inversions/solution/quan-ju-dao-zhi-yu-ju-bu-dao-zhi-by-leet-bmjp/