Easy

题目描述

给你一个数组 nums，如果这个数组原本是按非递减顺序排列，然后经过旋转某些位置（包括零次旋转）得到的，则返回 true；否则，返回 false。

原数组中可能存在重复元素。

注意： 数组 A 旋转 x 个位置的结果是数组 B，其长度相同，且 B[i] == A[(i+x) % A.length]，对于每个有效的索引 i 都成立。

示例 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

解题思路

解题思路

这道题的关键是理解什么是"排序后旋转"的数组特点。

核心观察： 一个排序后旋转的数组最多只能有一个"断点"，即 nums[i] > nums[i+1] 的位置。

分析思路：

  1. 计数断点法（推荐）： 统计数组中有多少个位置满足 nums[i] > nums[(i+1) % n]（使用取模处理环形）

    • 如果断点数 > 1，说明不可能是排序后旋转得到的
    • 如果断点数 = 0，说明数组本身就是有序的
    • 如果断点数 = 1，还需要验证首尾是否满足旋转条件：nums[0] >= nums[n-1]

  2. 暴力枚举法： 枚举每个可能的旋转起始位置，检查是否能构成有序数组（时间复杂度较高）

实现细节：

  • 使用取模运算 (i+1) % n 来处理数组末尾到开头的环形连接
  • 断点计数为1时，需要额外检查 nums[0] >= nums[n-1]，确保旋转后的数组首元素不小于尾元素

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    bool check(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
        }
        
        return count <= 1;
    }
};

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

public class Solution {
    public bool Check(int[] nums) {
        int n = nums.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
        }
        
        return count <= 1;
    }
}

var check = function(nums) {
    const n = nums.length;
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        if (nums[i] > nums[(i + 1) % n]) {
            count++;
        }
    }
    
    return count <= 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目