在Python中检查数组是否排序且旋转

在Python中，检查一个数组是否已排序且旋转可能是一个常见的问题。这种情况下，我们需要确定数组是否按照单调增加或单调递减的方式排序，以及它是否经过了旋转。在这篇文章中，我们将介绍如何在Python中解决这个问题。

示例

让我们先看一个示例，以更好地理解这个问题。假设我们有一个由不重复的整数组成的数组 nums，它最初是升序排列的，但随后被旋转了一些位置。我们需要使用Python编写一个方法来检查它是否按照单调递增或单调递减的方式排序并旋转。

下面的代码是一个解决方案。它首先找到了数组中的最小值，并将数组分成两个部分：左侧和右侧。接下来，它分别检查这两个部分是否按照单调递增或单调递减的方式排序并旋转。如果两个部分同时满足这些条件，则数组被认为是排序且旋转的。否则，它被认为不是。

def check_sorted_rotated(nums):
    n = len(nums)
    # 找到最小的元素，即旋转点
    min_index = nums.index(min(nums))
    # 检查左侧部分是否按照单调递增的方式排序并旋转
    is_left_sorted_rotated = True
    for i in range(1, min_index):
        if nums[i] < nums[i-1]:
            is_left_sorted_rotated = False
            break
    # 检查右侧部分是否按照单调递减的方式排序并旋转
    is_right_sorted_rotated = True
    for i in range(min_index+1, n):
        if nums[i] > nums[i-1]:
            is_right_sorted_rotated = False
            break
    # 返回结果
    return is_left_sorted_rotated and is_right_sorted_rotated

现在，我们可以使用 check_sorted_rotated 方法来检查一个数组是否排序且旋转了，如下所示：

# 示例 1
nums = [4, 5, 6, 7, 0, 1, 2]
print(check_sorted_rotated(nums)) # True

# 示例 2
nums = [1, 2, 3, 4, 5, 6, 7]
print(check_sorted_rotated(nums)) # False

在这个例子中，示例1 的数组已排序且旋转了，因此返回值是 True。示例2 的数组是按单调递增方式排序的，而没有旋转，因此返回值是 False。

解释

现在，我们来解释一下上面这个方法的工作原理。

我们首先找到数组中的最小元素，它是旋转点。在示例1中，旋转点是数字0。然后我们将数组分成两部分：左侧和右侧。在示例1中，左侧部分是[4, 5, 6, 7]，右侧部分是[0, 1, 2]。

接下来，我们检查左侧部分是否按单调递增的方式排序并旋转。我们使用一个for循环迭代数组中的每个元素（除了第一个元素），并检查它是否大于等于前一个元素。如果我们发现某个元素违反了这个条件，则数组没有按单调递增的方式排序并旋转。在示例1中，左侧部分按单调递增的方式排序并旋转，因为它包括数字4, 5, 6, 7，都是按递增顺序排列的。

然后，我们检查右侧部分是否按单调递减的方式排序并旋转。类似于检查左侧部分，我们使用一个for循环迭代数组中的每个元素（除了旋转点），并检查它是否小于等于前一个元素。如果我们发现某个元素违反了这个条件，则数组没有按单调递减的方式排序并旋转。在示例1中，右侧部分按单调递减的方式排序并旋转，因为它包括数字0, 1, 2，都是按递减顺序排列的。

最后，我们将这两个条件组合起来，并返回它们的“并”的结果。如果它们同时为 True，则数组被认为是已排序并旋转的。否则，它被认为不是。