在 LeetCode 上检查数组是否已排序和旋转

Question

我完全被这个问题困扰了。我试图用

std::is_sorted

和

std::is_sorted_until

来解决它，这是我的代码：

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}

失败？枢轴是第二项，它没有排序，但

std::is_sorted(nums.begin(), pivot)

在我测试时返回 true：

int main()
{
    Solution   sol;
    std::vector v{2, 1, 3, 4};

    const auto pivot = std::is_sorted_until(v.begin(), v.end());
    std::cout << std::distance(v.begin(), pivot) << '\n'; // The index of the pivot.

    // Why it prints true???
    std::cout << std::boolalpha << std::is_sorted(v.begin(), pivot) << '\n';

    // Prints true?
    std::cout << std::boolalpha << std::is_sorted(pivot, v.end()) << '\n';

    // Should print false but it prints true.
    std::cout << std::boolalpha << sol.check(v) << '\n';
}

我尝试修改迭代器输入，尤其是结束迭代器。谢谢。

Answer 1

有两个问题：

1. pivot

   将指向未排序的 first 值，因此它引用属于向量第二个分区的 first 值。因此测试不应该是

   std::is_sorted(pivot + 1, nums.end())

   ，而是

   std::is_sorted(pivot, nums.end())

2. 即使两个分区已排序，也不意味着它是已排序序列的旋转。这个例子证明了这一点：给定

   {2, 1, 3, 4}

   ，

   {2}

   已排序，

   {1, 3, 4}

   也已排序，但总计不是已排序序列的旋转。这是因为分区具有“重叠”的顺序。您需要第三个条件，即向量中的 last 值不大于 first。

所以最后的

return

声明应该是：

            return nums.back() <= nums[0] &&
                   std::is_sorted(nums.begin(), pivot) &&
                   std::is_sorted(pivot, nums.end());