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

题目描述

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但 按非递减顺序排列。nums 中的元素可能会被轮转（向左移动）若干次。

思路:遍历

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

有序数组经过旋转得到的数组的性质

  1. 旋转后的数组中，最多只有一个逆序对（这道题是前一个元素大于后一个元素）。
  2. 旋转后的数组的第一个元素和最后一个元素可以抽象成相邻的，也需要判断是否逆序

代码

class Solution:
    def check(self, nums: List[int]) -> bool:
        inversion_cnt = 0 if nums[0] >= nums[-1] else 1

        for i in range(len(nums) - 1):
            if nums[i] > nums[i+1]:
                inversion_cnt += 1
                if inversion_cnt > 1:
                    return False

        return True

更优雅的解法

import itertools

class Solution:
    def check(self, nums: List[int]) -> bool:
        is_sorted = nums[0] >= nums[-1]

        for x,y in pairwise(nums):
            if x > y:
                if not is_sorted:
                    return False
                is_sorted = False

        return True