What is a simple method to check if an array is sorted and rotated?

Count descending pairs in a single pass and ensure there is at most one, including wrap-around from the last to the first element.

Does this method work with duplicate elements?

Yes, duplicates do not increase descending pairs unless they violate non-decreasing order.

What if the array is already sorted and not rotated?

The algorithm treats zero rotations as valid, so a fully sorted array returns true.

Can this approach handle arrays of length 1 or 2?

Yes, arrays with one or two elements are always considered sorted and possibly rotated.

Is there a more efficient approach than O(n) for this problem?

No, any method must at least examine each element to check the descending pair count, so O(n) is optimal.

#1752

Easy

auto_awesome数组·driven

LeetCode 题解工作台

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

给你一个数组 nums 。 nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。源数组中可能存在重复项。注意：数组 A 在轮转 x 个位置后得到长度相同的数组…

数组

题目描述

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

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

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

注意：数组 A 在轮转 x 个位置后得到长度相同的数组 B ，使得对于每一个有效的下标 i，满足 B[i] == A[(i+x) % A.length]。

示例 1：

输入：nums = [3,4,5,1,2]
输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 2 个位置，使新数组从值为 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

lightbulb

解题思路

方法一：一次遍历

要满足题目要求，那么数组 nums 中最多只能存在一个元素，其值大于下一个元素，即 $nums[i] \gt nums[i + 1]$ 。如果存在多个这样的元素，那么数组 nums 无法通过轮转得到。

注意，数组 nums 最后一个元素的下一个元素是数组 nums 的第一个元素。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 nums 的长度。

1

2

3

4

class Solution:
    def check(self, nums: List[int]) -> bool:
        return sum(nums[i - 1] > v for i, v in enumerate(nums)) <= 1

speed

复杂度分析

指标	值
时间	complexity is O(n) because we traverse the array once. Space complexity is O(1) since we only track a counter for descending pairs and use no additional data structures.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Watch for multiple descending points indicating invalid rotation.
question_mark
Check wrap-around comparisons at the array boundaries carefully.
question_mark
Handle duplicates correctly to avoid miscounting descending pairs.

warning

常见陷阱

外企场景

error
Failing to count the descending pair between the last and first element.
error
Assuming zero rotation must be ignored, which can cause false negatives.
error
Overlooking duplicate elements that do not break the sorted rotation property.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine if an array is strictly increasing and rotated without duplicates.
arrow_right_alt
Check if an array can be sorted in non-increasing order and rotated.
arrow_right_alt
Find the minimum number of rotations needed to make an array sorted.

help

常见问题

外企场景

继续练习

#1751 最多可以参加的会议数目 II #1749 任意子数组和的绝对值的最大值 #1755 最接近目标值的子序列和