题目描述
给定一个数组 nums
。nums
的源数组中,所有元素与 nums
相同,但按非递减顺序排列。
如果 nums
能够由源数组轮转若干位置(包括 0 个位置)得到,则返回 true
;否则,返回 false
。
源数组中可能存在 重复项。
注意:我们称数组 A
在轮转 x
个位置后得到长度相同的数组 B
,当它们满足 A[i] == B[(i+x) % A.length]
,其中 %
为取余运算。
样例
输入:nums = [3,4,5,1,2]
输出:true
解释:[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 3 个位置,使新数组从值为 3 的元素开始:[3,4,5,1,2]。
输入:nums = [2,1,3,4]
输出:false
解释:源数组无法经轮转得到 nums。
输入:nums = [1,2,3]
输出:true
解释:[1,2,3] 为有序的源数组。
可以轮转 x = 0 个位置(即不轮转)得到 nums。
输入:nums = [1,1,1]
输出:true
解释:[1,1,1] 为有序的源数组。
轮转任意个位置都可以得到 nums。
输入:nums = [2,1]
输出:true
解释:[1,2] 为有序的源数组。
可以轮转 x = 5 个位置,使新数组从值为 2 的元素开始:[2,1]。
限制
1 <= nums.length <= 100
1 <= nums[i] <= 100
算法
(遍历数组) $O(n)$
- 找到第一个递减的位置。如果不存在则返回
true
。 - 从第一个递减的位置开始,检查之后是否还存在递减的位置。如果还存在则返回
false
。 - 判断最后一个元素是否小于等于第一个元素。
时间复杂度
- 遍历数组一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool check(vector<int>& nums) {
const int n = nums.size();
int d = -1;
for (int i = 0; i < n - 1; i++)
if (nums[i] > nums[i + 1]) {
d = i + 1;
break;
}
if (d == -1)
return true;
for (int i = d; i < n - 1; i++)
if (nums[i] > nums[i + 1])
return false;
return nums[n - 1] <= nums[0];
}
};