检查两个数组是否具有相同顺序的元素

Question

如何检查两个数组（循环）是否具有相同顺序的元素。例如，让我们来看看数组[1,2,3,4]。

该测试应该为[2,3,4,1]，[3,4,1,2]，[4,1,2,3]返回true，但不适用于[1,3,2,4 ]，[1,4,2,3]或[1,2,3,5]。

我最初的做法是找到第一个匹配 - 每个数组中的一个元素是相等的 - 并将这两个元素作为它们各自数组的初始元素，我将逐个比较剩余的数组元素。

有没有更好的方法？ 谢谢。

Answer 1

如果一个数组是循环的，那么array+array就是整个数组的另一部分。 例如：

[2 3 4 1] append [2 3 4 1] = [2 3 4 1 2 3 4 1] 
            |-------| 

，你可以看到[1 2 3 4]是“某处”在同一个阵列的追加两倍。

因此，通过这个逻辑，你可以做一个O(n*m)操作，检查每一种情况下，看它是否匹配（n为数组1和m为数组2）：

//array1 has [2 3 4 1 2 3 4 1] 
//array2 has [1 2 3 4] 
boolean check = false; 
for(int i = 0; i < array1.length(); i++) { 
    for(int j; j < array2.length(); j++) { 
     if((i+j) <= array1.length()) { 
     if(array1[i+j] == array2[j]) 
      check = true; 
     else 
      check = false; 
     } 
    } 
    if(check) 
     return true; // returns true if all array2 == some part of array1 
} 
return false; 

您还可以检查出Boyer-Moore algorithm到改善这一点。它用于字符串匹配，但是可以在这里应用相同的逻辑。

基本思想是有一个array2查找表，并能够“跳过”你知道你不必再次检查的值。

1 2 3 4 5 6 
3 4 5 
^-------^ lookup table sees that the offset is 3 to match array2[0] with array1[2] 

    1 2 3 4 5 6 
skip to--->3 4 5 
    would be the next iteration 

Answer 2

假设这个算法可以帮助你。

public void test() { 
    int[] a1 = {1,2,3,4}; 
    int[] a2 = {2,3,4,5}; 
    int[] a3 = {2,3,4,1}; 
    if (calculateDifference(a1, a2)) { 
     System.out.println("a1 has same elements order to a2"); 
    } 
    if (calculateDifference(a1, a3)) { 
     System.out.println("a1 has same elements order to a3"); 
    } 
    if (calculateDifference(a2, a3)) { 
     System.out.println("a2 has same elements order to a3"); 
    } 
} 
private boolean calculateDifference(int[] a1,int[] a2){ 
    int total = 0; 
    boolean match = false; 
    if (a1.length != a2.length) { 
     return match; 
    } 
    for (int i = 0; i < a1.length; i++) { 
     int a1Num = a1[i]; 
     int a2Num = a2[i]; 
     total += a1Num - a2Num; 
    } 
    if (total == 0) { 
     match = true; 
    } 
    return match; 
} 

Answer 3

如果没有允许重复你只需要找到第二阵列中等于第一第一阵列的另一个元件，并从那里检查它们，溶液是O（n）：

boolean areEquivalent(int[] array1, int[] array2) { 
    int i1 = 0, i2 = 0; 
    for (; i2 < array2.length; ++i2) 
    if (array2[i2] == array1[i1]) 
    break; 

    // no element found in common, they can't be equivalent 
    if (i2 == array2.length) 
    return false; 

    for (int j = 0; j < array1.length; ++j) 
    if (array1[i1+j] != array2[(i2+j) % array2.length] 
     return false; 

    return true; 
} 

如果允许重复，您必须考虑到i1和i2可以从不同的点开始并尝试所有这些，如果最后的for失败，则应该将i1更改为从第二次出现相同值开始，依此类推。完成此操作后，您必须再次更改i2 e，因此不同的方法（如Jay提议的方法）会更好。

Answer 4

我已经试过这样的，它的工作原理：

int a[] = {2,3,4,1}; 
    int b[] = {3,4,1,2}; // return true for these input 

    boolean check = false; 
    for (int i = 0; i < a.length; i++) { 
     int tmp = b[0]; 
     System.arraycopy(b, 1, b, 0, b.length - 1); 
     b[b.length - 1] = tmp; 
     if (Arrays.equals(a, b)) { 
      check = true; 
      System.out.println("Output: " + Arrays.equals(a, b)); 
     } 
    } 
    if (!check) { 
     System.out.println("Output: false"); 
    }