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

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

隔离第三天，以暴制暴

啊啊啊啊 隔离三天把周赛都忘得一干二净

（校园网都进不去，只能开个热点）

两次遍历：寻找最小元素的下标

• 思路：先遍历一遍数组，记录数组中最小元素的下标minIndex；然后再从minIndex遍历一遍数组，判断数组是否是升序排序，一旦遇到当前元素大于下一个元素，返回false。

• 实现：

由于数组当中存在重复元素，在寻找最小元素的下标minIndex应该记录所有元素升序排序时的第一个最小元素下标，因此当nums[i]≤nums[minIndex]时，更新minIndex，此时还应判断后面是否有重复元素

。若有则跳过这些元素，不更新minIndex，如测试用例n u m s = [ 7 , 9 , 1 , 1 , 1 , 3 ] nums=[7,9,1,1,1,3]nums=[7,9,1,1,1,3]

。若无则继续判断下一元素，若再次碰到元素与最小值相等，应更新minIndex，如测试用例nums=[ 6 , 10 , 6 ] [6,10,6][6,10,6]

• 代码

class Solution {
    public boolean check(int[] nums) {
        int minIndex = 0;// 记录第一个最小值的下标
        int len = nums.length;
        for (int i = 0; i < len; i++){
            if (nums[i] <= nums[minIndex]){
                minIndex = i;
                while (i + 1 < len && nums[i + 1] == nums[i]){
                    i++;
                }
            }
        }
        for (int i = minIndex; i < minIndex + len - 1; i++){
            if (nums[i % len] > nums[(i + 1) % len]){
                return false;
            }
        } 
        return true;
    }
}

。复杂度

• 时间复杂度：O ( n )

• 空间复杂度：O ( 1 )

一次遍历：寻找轮转位置

• 思路：首先判断数组是否进行了轮转，如果未进行轮转，那么只需要判断nums是否为递增；如果进行了轮转，则以轮转位置为分界线，如果两个子数组均为递增顺序，并且后一个子数组中的所有元素均小于等于前一数组中的所有元素，则返回true

• 实现

。首先找到数组中第一个i ii满足nums[i]<nums[i−1]，i ii即为数组向右轮转的位置

。如果i=0，那么代表数组nums是递增的，返回true

。如果i!=0那么此时可以将nums划分为两个子数组：

• nums[0,i−1]：一定是递增的

• nums[i,len−1]：不一定是递增的

。然后判断nums[i,len−1]是否是递增的

• 如果不是递增的，那么直接返回false

• 如果是递增的，当nums[i,len−1]中所有元素小于等于nums[0,i−1]总所有元素时，数组nums符合条件

• 由于这两个子数组均为递增，因此只需要判断nums[lem−1]是否小于等于nums[0]即可

• 代码

class Solution {
    public boolean check(int[] nums) {
        int n = nums.length, x = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                x = i;
                break;
            }
        }
        if (x == 0) {
            return true;
        }
        for (int i = x + 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return nums[0] >= nums[n - 1];
    }
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/check-if-array-is-sorted-and-rotated/solutions/1990942/jian-cha-shu-zu-shi-fou-jing-pai-xu-he-l-cbqk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

。复杂度

• 时间复杂度：O ( n )
• 空间复杂度：O ( 1 )