题目描述
给你一个数组 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
算法分析
- 将给定的数组中的所有轮转情况列举出来,判断所有轮转情况中是否存在一种满足非递减顺序排列的情况
例如:[3,4,5,1,2]
非递减顺序排列 是 [1,2,3,4,5]
轮转情况1: [3,4,5,1,2]
轮转情况2:[4,5,1,2,3]
轮转情况3: [5,1,2,3,4]
轮转情况4: [1,2,3,4,5] (满足非递减顺序排列)
轮转情况5: [2,3,4,5,1]
时间复杂度 $O(n^2)$
参考文献
y总
C++ 代码
class Solution {
public:
bool check(vector<int>& a) {
int n = a.size();
vector<int> b = a;
sort(b.begin(), b.end());
for(int i = 0;i < n;i ++)
{
if(a == b) return true;
int t = a[0];
for(int j = 1;j < n;j ++)
a[j - 1] = a[j];
a.back() = t;
}
return false;
}
};