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

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]则不返回true。

我最初的方法是找到第一个匹配项——每个数组中一个相等的元素——并将这两个元素视为各自数组的初始元素，我逐个比较了数组的其余元素。

有没有更好的办法？非常感谢。

Answer 1

如果不允许重复，只需在第二个数组中找到与第一个数组中的第一个数组相等的另一个元素，然后从那里检查它们，解决方案是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都可以从不同的点开始并尝试所有它们，如果的最后一个失败，您应该更改i1以从相同值的第二次出现开始，依此类推。完成此操作后，您必须再次更改i2e重试，因此不同的方法（如Jay提出的方法）会更好。

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

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

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

正如您所看到的，同一数组的两次追加中的“某处”。

因此，通过这个逻辑，您可以执行一个O（n*m）操作，检查每个案例是否匹配（n为array1，m为array2）：

 //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算法来对此进行改进。它用于字符串匹配，但这里可以应用相同的逻辑。

其基本思想是有一个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