一、题目
给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。
源数组中可能存在 重复项 。
注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。
二、示例
2.1> 示例 1：
【输入】nums = [3,4,5,1,2]
【输出】true
【解释】[1,2,3,4,5] 为有序的源数组。可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。
2.2> 示例 2：
【输入】nums = [2,1,3,4]
【输出】false
【解释】源数组无法经轮转得到 nums 。
2.3> 示例 3：
【输入】nums = [1,2,3]
【输出】true
【解释】[1,2,3] 为有序的源数组。可以轮转 x = 0 个位置（即不轮转）得到 nums 。
提示：
-
1<= nums.length <=100 -
1<= nums[i] <=100
三、解题思路
根据题目描述我们可以知道，nums的源数组其实就是一个“递增”数组，那么如果nums数组可以由源数组轮转若干位置（包括 0 个位置）得到，则返回true，否则返回false。那么针对于返回true的情况，我们其实可以总结如下两种情况：
【情况1】如果
nums数组中的元素就是“递增”的，则说明由源数组轮转0个位置可以得到nums数组。
【情况2】如果在nums数组中，仅仅有1次“非递增” 的情况发生，那么需要满足nums[0] >= nums[nums.length - 1]，才会返回true。
针对于以上描述的两种情况的具体解释，请见下图所示：
其中，由于我们只需遍历一遍数组，所以时间复杂度为：O(n)，其中 n 表示nums数组的长度。
四、代码实现
class Solution {
public boolean check(int[] nums) {
int t = 0, n = nums.length;
for (int i = 1; i < n; i++) {
if (t > 1) return false; // 如果出现超过1次的“非递增”情况，则直接返回false
if (nums[i - 1] > nums[i]) t++; // 如果出现“非递增”情况，则t加1
}
return t == 0 || (t == 1 && nums[0] >= nums[n - 1]);
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论