檢查兩個數組是否具有相同順序的元素

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"); 
    }