LeetCode 1752：检查排序旋转数组的代码错误排查求助

题目回顾 #

给定数组nums，判断其是否由一个非递减排序的数组经过若干次（含0次）旋转得到。是则返回true，否则返回false。原数组允许存在重复元素。

旋转定义：数组A旋转x位得到数组B，满足A[i] == B[(i+x) % A.length]（%为取模运算）。

示例 #

• 输入nums = [3,4,5,1,2] → 输出true（原数组[1,2,3,4,5]旋转3位得到）
• 输入nums = [2,1,3,4] → 输出false（无对应排序旋转数组）
• 输入nums = [1,2,3] → 输出true（无需旋转）

你的代码问题 #

class Solution {
public:
    bool check(vector<int>& nums) {

        int n = nums.size();

        int Break = -1;

        for(int i = 0; i < n - 1; i++){
            if(nums[i] > nums[i + 1]){
                Break = i;
            }
        }

        if(Break == n - 1){
            return true;
        }

        else {
            for(int i = Break + 1; i < n - 1; i++){
                if(nums[i] > nums[i + 1]){
                    return false;
                }
            }
        }

        return true;
        
    }
};

核心错误点 #

1. 未处理环形首尾的衔接判断
   你的代码只检查了数组内部的下降点，但忽略了旋转数组的环形特性：当存在旋转断点时，数组最后一个元素必须小于等于第一个元素。比如测试用例[1,3,2]，你的代码会认为断点后子数组有序而返回true，但实际上该数组无法由非递减数组旋转得到（因为2 > 1，破坏了环形的非递减逻辑）。

2. 允许多个下降点存在
   符合条件的旋转数组最多只能有1个下降点（即nums[i] > nums[i+1]的情况仅出现一次）。但你的代码会记录最后一个下降点，忽略之前的下降点，比如测试用例[3,2,1]，你的代码会错误返回true，但该数组存在两个下降点，无法由非递减数组旋转得到。

3. 无效的判断条件Break == n-1
   循环i的范围是0 <= i < n-1，Break的最大值是n-2，永远不可能等于n-1，这段逻辑完全无效。

修正后的代码 #

class Solution {
public:
    bool check(vector<int>& nums) {
        int n = nums.size();
        int dropCount = 0;
        
        for (int i = 0; i < n; ++i) {
            // 环形比较当前元素与下一个元素（最后一个元素和第一个元素比较）
            if (nums[i] > nums[(i + 1) % n]) {
                dropCount++;
                // 超过1个下降点直接判定不符合
                if (dropCount > 1) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

修正逻辑说明 #

• 统计下降点数量：遍历数组时，通过(i+1)%n实现环形遍历，检查每一对相邻元素（包括首尾）的大小关系。
• 严格限制下降点数量：非递减数组旋转后，最多只会出现1次下降（旋转衔接处）；完全有序的数组则没有下降点。只要下降点数量超过1，直接返回false。

内容的提问来源于stack exchange，提问作者Sarvagya Kumar