java - 如何检查一个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

您可以遍历数组并检查所有值是否都在增加。一旦您找到第一个没有增加的值，请检查它和以下所有值是否都在增加并且小于或等于数组中的第一个元素。

编辑:

我觉得人们对 Daniel 的解决方案不以为然，因为他们不理解它或认为它有问题。这很可悲，因为我认为他的解决方案非常出色。

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

稍微解释一下。要检查列表是否循环排序，我最初的回答是您需要检查完全排序后是否有一个或更少的“中断”，并且“中断”之后的所有数字都小于数组中的第一个数字。

但是，正如 Daniel 的回答所示，您不需要检查“中断”后的所有数字，只需检查最后一个数字(这也恰好是中断后最大/最大的数字，因为它们已排序)。

应该总是有一个中断，除非列表中填满了相同的数字，在这种情况下不会有中断并且计数将为 0。