【LeetCode】1752.检查数组是否经排序和轮转得到

题目描述

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

示例 1&＃xff1a;

输入&＃xff1a;nums &＃61; [3,4,5,1,2]
输出&＃xff1a;true
解释&＃xff1a;[1,2,3,4,5] 为有序的源数组。
可以轮转 x &＃61; 3 个位置&＃xff0c;使新数组从值为 3 的元素开始&＃xff1a;[3,4,5,1,2] 。

示例 2&＃xff1a;

输入&＃xff1a;nums &＃61; [2,1,3,4]
输出&＃xff1a;false
解释&＃xff1a;源数组无法经轮转得到 nums 。

示例 3&＃xff1a;

输入&＃xff1a;nums &＃61; [1,2,3]
输出&＃xff1a;true
解释&＃xff1a;[1,2,3] 为有序的源数组。
可以轮转 x &＃61; 0 个位置&＃xff08;即不轮转&＃xff09;得到 nums 。

提示&＃xff1a;

1 <&＃61; nums.length <&＃61; 100
1 <&＃61; nums[i] <&＃61; 100

方法一&＃xff1a;我的解法

class Solution {
public:
bool check(vector<int>& nums) {
int pos &＃61; 0;
int n &＃61; nums.size();
vector<int> numsOrigin(n);
// 保存默认数组
for(int i&＃61;0; i<n ; i&＃43;&＃43;)
numsOrigin[i] &＃61; nums[i];

// nums为原数组
sort(nums.begin(), nums.end()); // 默认升序
// 确定目标元素的偏移量
for(int i&＃61;0; i<n; i&＃43;&＃43;){
// 条件1:当前数字与原数组不匹配
// 条件2:如果有若干连续的数字&＃xff0c;考虑最后一个
if(numsOrigin[i] !&＃61; nums[i] && numsOrigin[i] !&＃61; numsOrigin[(i&＃43;1) % n]){
// 目标元素
int flag &＃61; numsOrigin[i];
for(int j&＃61;0; j<n; j&＃43;&＃43;){
// 条件1:在排序数组中找到目标元素
// 条件2:如果有若干连续数字&＃xff0c;考虑最后一个
if(flag &＃61;&＃61; nums[j] && nums[j] !&＃61; nums[(j &＃43; 1)%n]){
// 确定偏移位置
pos &＃61; (j - i &＃43; n) % n;
break;
}
}
break;
}
}
for(int i&＃61;0; i<n; i&＃43;&＃43;){
if(numsOrigin[i] !&＃61; nums[(i &＃43; pos) % n]) return false;
}
return true;
}
};


方法二&＃xff1a;优秀题解

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


心得

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

• 解法一&＃xff1a;常规解法

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

• 重点在于 如何确定 目标元素 和 偏移量&＃xff1f;

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

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

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

参考资料&＃xff1a;

1. 【爪哇缪斯】图解LeetCode