检查两个数组是否是循环排列

Question

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

例如，给定 a = [1, 2, 3, 1, 5]、b = [3, 1, 5, 1, 2] 和 c = [2, 1, 3, 1, 5] 我们知道 a 和 b 是循环排列，但 c 是都不是循环排列。

注意：数组可能有重复的元素。

Answer 1

这里的标准技巧是将其中一个数组与其自身连接起来，然后尝试在连接的数组中找到第二个数组。

例如，“a”与其自身连接为：

[1, 2, 3, 1, 5, 1, 2, 3, 1, 5]

因为您确实在该数组中从第三个元素开始看到“b”，所以 a 和b 是循环排列。

Answer 2

如果 A 和 B 是彼此的循环排列，则 A 将在双列表 BB 中找到（就像 B 在 AA 中一样）。

Answer 3

处理大量数据的有效方法是将它们转换为“规范”形式，然后进行比较以查看它们是否相等。对于这个问题，您可以选择“排序最小”的排列作为所有旋转排列的规范形式。

因此，“a”和“b”的规范形式是 [1, 2, 3, 1, 5]，它们是相等的，因此它们是非循环排列。

“c”的规范形式是 [1, 3, 1, 5, 2]，这是不同的。

Answer 4

这是一种简单的临时方法，用于找出时间复杂度为 O(n) 的循环排列。

a = [1, 2, 3, 1, 5], b = [3, 1, 5, 1, 2]

在a[]中查找b[0]的索引，假设索引为'x'。然后开始
在两个数组中导航。 a[] 从索引 'x' 和 b[] 开始
从“0”开始。这样他们两个就必须具有相同的价值观。如果
不，它们不是循环的。
这是示例代码。

 public class CyclicPermutation {

    static char[] arr = { 'A', 'B', 'C', 'D' };
    static char[] brr = { 'C', 'D', 'K', 'B' };
    boolean dec = false;

    public static void main(String[] args) {
        boolean avail = true;
        int val = getFirstElementIndex(brr[0]);
        if(val ==Integer.MIN_VALUE){
            avail = false; 
            return;
            }

        for (int i = val, j = 0; j <= brr.length-1; ) {
            if (i > arr.length-1) {
                i = 0;
            }
            if (arr[i] == brr[j]) {
                i++;

                j++;

            } else {
                avail = false;
                System.out.println(avail);
                return;
            }


        }

   System.out.println(avail);
    }

    public static int getFirstElementIndex(char c) {

        for (int i = 0; i <= arr.length; i++) {
            if (arr[i] == c) {
                return i;
            }
        }
        return Integer.MIN_VALUE;
    }


}