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

arrays sorting java

2022-09-03 06:59:46

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

如果数组的元素除旋转外还对其进行了排序，则该数组将循环排序。

例如：

4 5 6 7 1 2 3

这里的元素是“按顺序”排列的，但它们向左旋转了三个。因此，如果我们向右旋转3，我们得到的是一个排序数组。1 2 3 4 5 6 71 2 3 4 5 6 7

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

答案 1

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

编辑：

我觉得人们低估了丹尼尔的解决方案，因为他们不理解它或认为它已经坏了。这很可悲，因为我认为他的解决方案非常出色。

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。

答案 2

如果一些用户想知道实现是什么样的。

public boolean isCircularSorted(int[] array)
{
    int size = array.length;
    int count = 0;

    for(int x=0; x<size; x++)
        if(array[x] > array[(x+1)%size])
            count ++;
    return (count <= 1);
}

用户丹尼尔也提到了这一点。