题目描述

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。
源数组中可能存在 重复项 。
注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。

示例 1：

输入：nums = [3,4,5,1,2]
输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 3 个位置，使新数组从值为 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

方法一：我的解法

class Solution {
public:bool check(vector& nums) {int pos = 0;int n = nums.size();vector numsOrigin(n);// 保存默认数组for(int i=0; i// 条件1:当前数字与原数组不匹配// 条件2:如果有若干连续的数字，考虑最后一个if(numsOrigin[i] != nums[i] && numsOrigin[i] != numsOrigin[(i+1) % n]){// 目标元素int flag = numsOrigin[i];for(int j=0; j// 条件1:在排序数组中找到目标元素// 条件2:如果有若干连续数字，考虑最后一个if(flag == nums[j] && nums[j] != nums[(j + 1)%n]){// 确定偏移位置pos = (j - i + n) % n; break;}}break;}}for(int i=0; iif(numsOrigin[i] != nums[(i + pos) % n])   return false;}return true;}
};

方法二：优秀题解

class Solution {
public:bool check(vector& nums) {int cnt = 0; // 记录非递增情况出现的次数int n = nums.size();for(int i=0; iif(nums[i] > nums[i+1]) cnt ++;}// nums已经是非递减数组，说明与原数组相同if(cnt == 0)    return true;// 仅发生了一次非递增// 并且第一个元素大于最后一个元素，说明首尾元素也是非递减的else if(cnt == 1 && nums[0] >= nums[n-1])   return true;// 不止一次非递增else return false;}
};

心得

• 这道题是11.27的每日一题，那天出去玩了，没做出来，今天补一下。这道题是简单题，但我的解法略微显得复杂，甚至我提交了很多次，最后在卡测试点才通过的，但是还是记录一下，更推荐看解法二。

• 解法一：常规解法

• 思路：由于 原数组是一个 递增 数组，因此我对 nums 进行了 sort 排序得到了原数组，之后就是确定一个 目标元素 ，确定目标元素在 「给定数组」 和 「原数组」之间的偏移量，最后在给定数组中遍历偏移量即可。

• 重点在于 如何确定 目标元素 和 偏移量？

  • 一开始我只考虑到了 条件1：找到第一个在「原数组」和「给定数组」中不同的元素。
    但是这个考虑不全面， 比如：
    • nums = [4, 5, 7, 7, 9, 9, 10, 10, 3, 4]，
      这个数组的原数组是 [3, 4, 4, 5, 7, 7, 9, 9, 10, 10]
    • 第一个不同的元素是 nums 中的第一个 4 ，但是很明显，我们可以发现第一个 4 应该对应的是 原数组中的第二个 4，然而我一开始给出的条件只能将第一个 4 对应到 原数组的第一个 4。
  • 因此，我在确定偏移量的部分加上了 条件2：如果有若干连续的数字，考虑最后一个。
    此时，上面的例子就能正确通过了，我们也确定了 目标元素。
  • 然而此时出现另外一种情况，比如：
    • nums = [5，5，6，6，6，9，1，2]，
      这个数组的原数组是 [1，2，5，5，6，6，6，9]
    • 第一个不同的元素应该是 第一个 5 ， 如果按照上面的两个逻辑，此时的第一个 5 会默认匹配到最后一个 5 ，那显然是不正确的，因此我在确定目标元素的部分加上了 条件2：如果有若干连续的数字，考虑最后一个。此时，这个例子的目标元素就是第二个 5 。

  综上所述，通过各两个条件，我们就能确定目标元素和偏移量。

• 方法二：
• 思路：对于 True，其实有两种情况：
  • 情况一： 如果给定数组已经是递增的，说明原数组轮转 0 个位置就可以得到给定数组；
  • 情况二： 如果在 nums 数组中，仅仅有一次「非递增」的情况发生，那么需要满足 nums[0] >= nums[nums.length -1]

参考资料：

1. 【爪哇缪斯】图解LeetCode