如何检查int数组是否是循环排序的数组？

Question

比方说我有一个整数数组{1, 3, 4, 7, -9, 0}.此数组是循环排序的,而数组{2, 4, 9 , 3}不是循环排序的.

如果对数组的元素进行排序(循环除外),则对数组进行循环排序.

例如:

4 5 6 7 1 2 3

这里的元素1 2 3 4 5 6 7是"按顺序",但它们向左旋转三个.因此,如果我们向右旋转3,我们得到的1 2 3 4 5 6 7是一个排序数组.

给定一个数组,如何检查数组是否循环排序？

Answer 1

您可以遍历数组并检查所有值是否都在增加.一旦你达到第一个没有增加的值,检查它和所有以下值是否正在增加AND小于或等于数组中的第一个元素.

编辑:

我觉得人们正在贬低丹尼尔的解决方案,因为他们不理解它或认为它已被打破.这很难过,因为我觉得他的解决方案很棒.

def is_circular_sorted(arr):
    count = 0
    length = len(arr)
    for i in range(length):
        if arr[i] > arr[(i+1) % len(arr)]:
            count += 1
    return count <= 1

In [4]: is_circular_sorted([1, 2, 3, 4])
Out[4]: True

In [5]: is_circular_sorted([1, 1, 1, 1])
Out[5]: True

In [6]: is_circular_sorted([1, 3, 4, 7, -9])
Out[6]: True

In [7]: is_circular_sorted([1, 3, 4, 2])
Out[7]: False

有一点解释.为了检查列表是否是循环排序的,我的原始答案说你需要检查是否有一个或更少的"中断"完全排序并且"中断"之后的所有数字都小于数组中的第一个数字.

然而,正如丹尼尔的答案所示,你不需要在"休息"之后检查所有数字,只需要检查最后一个数字(这也是休息后的最大/最大数字,因为它们已经排序).

应该总是有一个中断,除非列表中填充相同的数字,在这种情况下,没有中断,计数将为0.