[数组]leetcode1752：检查数组是否经排序和轮转得到(easy)

数组]leetcode1752：检查数组是否经排序和轮转得到(easy)"/>

[数组]leetcode1752：检查数组是否经排序和轮转得到(easy)

题目：

题解：

不要看本题是个 easy 题，但是它的最优解法并不是那么好想的。

---

思路1：

• 纯暴力，按题目意思，排序、翻转，然后判断是否相等就行。
• 时间复杂度 O ( n 2 ) O(n^2) O(n2)，空间复杂度 O ( n ) O(n) O(n)

---

思路2：

• 扫描这个数组看看是存在是否存在多少段单调序列，若只有1个或2个单调序列，表明数组是排序好的数组经过轮转得到的，这个用脑子模拟一下就行了。若存在2个以上的单调序列，表明数组是否非排序好的数组轮转得到的。注意还要比较第一个元素和最后一个元素的大小，把它看成一个圈的话，就是尾元素还要小于等于首元素的。我们用峰和谷的分界点表示单调序列的分界点，最后分界点的个数小于等于1时，表示满足题意，返回 true，否则返回 false。
• 时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)
  

代码如下：

class Solution {
public:// 解法1：直接暴力法做// 思路：直接将数组 a 进行排序得到数组 b，然后将 a 轮转看是否能得到排序好的 bbool check_1(vector<int>& a) {auto b=a;sort(b.begin(),b.end());int n=a.size();// 将a翻转n次，每次都将第一个元素移到最后面，判断翻转后a是否和排序好的b是否相等for(int i=0;i<n;++i){//rotate(a.begin(),a.begin()+1,a.end());// 换用代码实现int t=a[0];for(int j=1;j<n;j++)a[j-1]=a[j];a.back()=t;if(a==b)return true;}return false;}// 解法2：利用单调性做，由于源数组是单调数组，然后经过轮转后得到数组 a// 此使的数组 a 要么是两段有序序列，要是是一段有序序列，所以我们只需要遍历一次数组，统计峰与谷的交界的个数就行了// 同时还要将第一段的第一个数与第二段的最后一个书进行比较，只有 a[0]>=a[n-1] 才是符合条件的bool check(vector<int>& a){int cnt=0,n=a.size();for(int i=0;i<n-1;++i)if(a[i]>a[i+1])cnt++;if(a[0]<a[n-1])cnt++;return cnt<=1;}
};