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

Question

如何检查两个数组(循环)是否具有相同顺序的相同元素。 例如，我们以数组 [1,2,3,4] 为例。

对于 [2,3,4,1]、[3,4,1,2]、[4,1,2,3] 测试应返回 true，但对于 [1,3,2,4] 则不返回 true 、[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