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

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 是 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 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