数组]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;}
};
更多推荐
[数组]leetcode1752:检查数组是否经排序和轮转得到(easy)
发布评论