检查数组是否经排序和轮转得到【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.

隔离第三天，以暴制暴
啊啊啊啊 隔离三天把周赛都忘得一干二净
（校园网csdn都进不去，只能开个热点）

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

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

• 实现：

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

  • 若有则跳过这些元素，不更新minIndex，如测试用例nums=[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(n)O(n)
    • 空间复杂度：O(1)O(1)O(1)

一次遍历：寻找轮转位置

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

• 实现

  • 首先找到数组中第一个iii满足nums[i]
  • 如果i=0i=0i=0，那么代表数组numsnumsnums是递增的，返回true
  • 如果i!=0i!=0i!=0那么此时可以将numsnumsnums划分为两个子数组：
    • nums[0,i−1]nums[0,i-1]nums[0,i−1]：一定是递增的
    • nums[i,len−1]nums[i,len-1]nums[i,len−1]：不一定是递增的
  • 然后判断nums[i,len−1]nums[i,len-1]nums[i,len−1]是否是递增的
    • 如果不是递增的，那么直接返回false
    • 如果是递增的，当nums[i,len−1]nums[i,len-1]nums[i,len−1]中所有元素小于等于nums[0,i−1]nums[0,i-1]nums[0,i−1]总所有元素时，数组numsnumsnums符合条件
      • 由于这两个子数组均为递增，因此只需要判断nums[lem−1]nums[lem-1]nums[lem−1]是否小于等于nums[0]nums[0]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(n)O(n)
    • 空间复杂度：O(1)O(1)O(1)