检查数组是否经排序和轮转得到

难度: Easy

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。

如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。

源数组中可能存在 重复项 。

注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。

示例 1：

输入：nums = [3,4,5,1,2]
输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。

示例 2：

输入：nums = [2,1,3,4]
输出：false
解释：源数组无法经轮转得到 nums 。

示例 3：

输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 为有序的源数组。
可以轮转 x = 0 个位置（即不轮转）得到 nums 。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

Submission

运行时间: 24 ms

内存: 16.5 MB

class Solution:
    def check(self, nums: List[int]) -> bool:
        n = len(nums)
        x = 0
        for i in range(1, n):
            if nums[i] < nums[i - 1]:
                x = i
                break
        if x == 0:
            return True
        for i in range(x + 1, n):
            if nums[i] < nums[i - 1]:
                return False
        return nums[0] >= nums[-1]

Explain

这个解法是通过一次扫描数组来检查是否存在一个单一的下降点，这个下降点表明数组从这里开始被轮转。首先遍历数组，找到第一个元素对(nums[i], nums[i-1])，使得nums[i] < nums[i-1]，这意味着数组在这里发生了旋转。如果没有发现这样的对，则数组是非递减的，直接返回true。找到旋转点后，检查从旋转点开始到数组结束之间的元素是否保持非递减顺序，如果这些元素依旧非递减并且数组的最后一个元素不大于数组的第一个元素，则返回true；否则返回false。

时间复杂度: O(n)

空间复杂度: O(1)

# 定义一个检查函数，接收一个整数数组

class Solution:
    def check(self, nums: List[int]) -> bool:
        n = len(nums)  # 数组长度
        x = 0  # 初始化旋转点索引
        # 寻找旋转点
        for i in range(1, n):
            if nums[i] < nums[i - 1]:
                x = i
                break
        # 如果没有找到旋转点，说明数组整体非递减
        if x == 0:
            return True
        # 检查从旋转点到数组末尾的元素是否非递减
        for i in range(x + 1, n):
            if nums[i] < nums[i - 1]:
                return False
        # 确保旋转后的数组第一个元素不小于最后一个元素
        return nums[0] >= nums[-1]

Explore

在一个被排序后通过轮转得到的数组中，最多只会出现一个下降点。这是因为轮转操作相当于将数组从某一点断开然后将前半部分移至数组尾部。这种操作保证了除了一个潜在的断点外，数组的其余部分保持原有的排序顺序。因此，如果通过扫描发现超过一个下降点，那么数组不可能只通过一次轮转操作从一个排序数组变换而来。

如果数组中存在重复的最大元素，可能会在判断是否只有一个下降点时出现误判。例如在数组 [2,2,3,3,1,2] 中，实际上存在两个下降点（一个在3到1之间，另一个在1到2之间），这违反了只有一个下降点的规则。因此，根据当前的算法逻辑，这个数组应该返回 false，因为它不能通过单一的排序和轮转操作得到。

在找到旋转点后，需要验证旋转点到数组末尾之间的元素保持非递减顺序来确保这部分是原数组中的一个连贯部分且未被修改（除了轮转操作外）。如果这部分元素没有保持非递减顺序，那么表示数组可能经过了其他类型的修改，或者旋转操作不仅仅是一个简单的头部到尾部的移动，从而导致不能通过简单的轮转来还原到一个完全排序的数组。

这个假设在原数组是非严格递增（即允许重复元素）时可能不成立。例如，如果原数组中包含相同的最小和最大元素，且这些元素在轮转后的数组两端出现，那么最后一个元素可能等于甚至大于第一个元素。此外，如果数组中所有元素均相等，那么任何位置的旋转都会使最后一个元素等于第一个元素，这也不符合假设。