LeetCode 1752：判断排序后旋转数组的C++解法问题排查

问题说明 #

给定数组nums，判断其是否为一个非递减排序数组经过若干次旋转（包括0次）得到的，数组允许包含重复元素。

注：数组A旋转x个位置后得到数组B，满足A[i] == B[(i+x) % A.length]，其中%为取模运算。

错误代码 #

class Solution
{
public:
    bool check(const std::vector<int>& nums)
    {
        // If the array is sorted without rotation.
        if (const auto pivot = std::is_sorted_until(nums.begin(), nums.end());
            pivot == nums.end())
        {
            return true;
        }
        // If there is a rotation, pivot will be our
        // point of rotation.
        else
        {
            // Check both halves.
            /**
             *     pivot
             *   ~~~~| 
             *   3 4 5 1 2 3
             *   ~~~~~       -> first half
             *         ~~~~~ -> second half
            */
            return std::is_sorted(nums.begin(), pivot) &&
                   std::is_sorted(pivot + 1, nums.end());
        }
    }
};

错误原因 #

针对输入{2, 1, 3, 4}的误判，核心问题有三点：

1. 缺少旋转数组的收尾衔接检查：原代码仅验证前后两段各自有序，但旋转数组要求后半段的最后一个元素必须小于等于前半段的第一个元素（对应原非递减数组的首尾衔接）。对于{2,1,3,4}，后半段[3,4]的最后一个元素4大于前半段第一个元素2，不符合旋转要求，但原代码未做此检查。
2. 后半段检查范围错误：原代码用pivot + 1作为后半段起始，实际上pivot是第一个破坏非递减顺序的位置，后半段应从pivot开始检查是否有序（比如pivot指向1时，后半段是[1,3,4]，本身是有序的，但原代码跳过了pivot元素，检查[3,4]，逻辑上存在漏洞）。
3. 冗余的前半段检查：std::is_sorted_until返回的pivot本身就保证了nums.begin()到pivot是有序的，无需再调用std::is_sorted验证。

修正后的代码 #

class Solution
{
public:
    bool check(const std::vector<int>& nums)
    {
        auto pivot = std::is_sorted_until(nums.begin(), nums.end());
        // 数组本身是非递减的，直接返回true
        if (pivot == nums.end())
        {
            return true;
        }
        // 检查后半段是否有序，且收尾元素满足旋转要求
        return std::is_sorted(pivot, nums.end()) && nums.back() <= nums.front();
    }
};

修正说明 #

• 移除冗余的前半段有序检查，利用is_sorted_until的特性减少不必要的计算。
• 修正后半段的检查范围，从pivot开始验证有序性，确保逻辑完整。
• 增加nums.back() <= nums.front()的判断，保证旋转数组的首尾衔接符合原非递减数组的要求，这是原代码最核心的缺失条件。

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