题目描述
LeetCode 1752 — 检查数组是否经排序和轮转得到 (Easy)
给你一个数组 nums，判断它是否能够由一个非递减排序的源数组轮转若干位置（包括 0 个位置）得到。轮转的定义：将数组 A 的元素整体向右移动 x 个位置，超出末尾的元素循环回到开头，即 A[i] == B[(i+x) % A.length]。
示例 1：
- 输入：
nums = [3,4,5,1,2] - 输出：
true - 解释：源数组
[1,2,3,4,5]轮转 3 个位置后得到[3,4,5,1,2]。
示例 2：
- 输入：
nums = [2,1,3,4] - 输出：
false - 解释：无论怎么轮转非递减数组，都无法得到
[2,1,3,4]——因为2之后紧接着1是一次下降，1之后又升到3再下降，出现两次非递增。
示例 3：
- 输入：
nums = [1,2,3] - 输出：
true - 解释：本身已是非递减的，相当于轮转 0 次。
约束：
1 <= nums.length <= 1001 <= nums[i] <= 100
求解思路
先想一个已经排好序的非递减数组长什么样——从头走到尾，每一步都是 nums[i] >= nums[i-1]，也就是不会出现下降。现在把这个数组轮转一下，相当于从中间某个位置切开，把前半段搬到末尾。比如 [1,2,3,4,5] 从 3 和 4 之间切开，得到 [4,5,1,2,3]——前半段是 [4,5]，后半段是 [1,2,3]，两段内部各自仍然非递减，但两段之间产生了一次下降：5 → 1。
换句话说，轮转操作最多在数组中引入一处下降点，即那个轮转切口的位置。而且这个切口之外，数组其他位置依然保持非递减。不仅如此——正因为切口把最小值挪到了后半段开头，数组的第一个元素一定不会小于最后一个元素（nums[0] >= nums[n-1]），因为首元素来自源数组的后半段，尾元素来自源数组的前半段。
于是判断逻辑就很清晰了：从头到尾检查相邻元素，统计 nums[i] < nums[i-1] 的下降次数。如果出现超过一次下降，说明至少有两个切口，不可能是一个纯轮转的结果，直接返回 false。如果恰好一次下降，需要用 nums[0] >= nums[n-1] 确认切口位置合理——首尾满足这个条件时，让这唯一一次下降充当切口即可。如果零次下降，数组本身就是有序的，轮转 0 次同样成立。
全相等元素的特殊情况也会被正确处理：既不会出现下降，nums[0] >= nums[n-1] 也天然成立。
解法：一次遍历
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool check(vector<int>& nums) {
int n = nums.size();
// 首尾关系标记是否可能是轮转数组（零次下降时也兼容）
bool isRotate = nums[0] >= nums[n - 1];
for (int i = 1; i < n; i++) {
if (nums[i] < nums[i - 1]) { // 发现一次下降
if (isRotate) isRotate = false; // 用掉唯一的切口名额
else return false; // 已经是第二次下降了
}
}
return true;
}
};
复杂度： 时间 O(n)，一次遍历；空间 O(1)，只用了常数额外变量。
变式：允许重复元素的轮转搜索
如果题目从判断合法性变为在轮转排序数组中搜索某个 target，则需要结合二分搜索处理切口。切口将数组分为两段有序区间，先判断 target 落在哪一段，再对该段做标准二分——这正是 LeetCode 33 的解法思路。
// 在轮转排序数组中搜索 target
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) { // mid 在左半段
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else { // mid 在右半段
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}