如何檢查一個數組是否是另一個數組的子序列？

我期待探索不同的算法，遞歸和動態編程，檢查如果一個arrayA是arrayB的子序列。例如，如何檢查一個數組是否是另一個數組的子序列？

arrayA = [1, 2, 3] 
arrayB = [5, 6, 1, 7, 2, 9, 3] 

thus, arrayA is indeed a subsequence of arrayB.

我已經嘗試了幾種不同的搜索，但我似乎找到是算法計算最長遞增子。

來源

2015-10-16 Talen Kylon

您需要高效的解決方案嗎？ – svs

@svs是的效率在這裏很重要。 –

因此，在'arrayB'中查找的元素總是與'arrayA'的順序相同？ – Sylwester

既然你必須匹配的arrayA到arrayB一些元素所有元素，你永遠不需要回溯。換句話說，如果arrayB中有兩個候選人與arrayA的元素相匹配，則可以選擇最早的候選人，並且不要收回選擇。

因此，你不需要DP，因爲一個簡單的線性貪婪策略將工作：

bool isSubsequence(int[] arrayA, int[] arrayB) { 
    int startIndexB = 0; 
    foreach (int n in arrayA) { 
     int next = indexOf(arrayB, startIndexB , n); 
     if (next == NOT_FOUND) { 
      return false; 
     } 
     startIndexB = next+1; 
    } 
    return true; 
}

來源

2015-10-16 16:26:10 dasblinkenlight

這是一個聰明的解決方案，但有什麼方法可以通過DP或遞歸更快地完成它？ –

@TalenKylon一般來說，除非你需要回溯，否則DP永遠不會有幫助。這是一個O（Na + Nb）解，其中Na和Nb是'arrayA'和'arrayB'的元素數。這個算法可以用O（1）存儲器中的僅前向迭代器實現。同一個項目永遠不會被查看一次以上，這意味着解決方案是漸近的。 – dasblinkenlight

由於dasblinkenlight正確地說，（我不可能話來說比他更好的答案!!）貪婪做法絕對沒問題。你可以使用下面的僞代碼（只需要更多的解釋，但完全類似於dasblinkenlight所寫的內容），這與合併兩個排序後的數組很相似。

A = {..} 
B = {..} 

j = 0, k = 0 
/*j and k are variables we use to traverse the arrays A and B respectively*/ 

for(j=0;j<A.size();){ 

    /*We know that not all elements of A are present in B as we 
     have reached end of B and not all elements of A have been covered*/ 
    if(k==B.size() && j<A.size()){ 
     return false; 
    } 

    /*we increment the counters j and k both because we have found a match*/    
    else if(A[j]==B[k]){ 
     j++,k++; 
    } 

    /*we increment k in the hope that next element may prove to be an element match*/   
    else if(A[j]!=B[k]){ 
     k++; 
    } 
} 

return true; /*cause if we have reached this point of the code 
       we know that all elements of A are in B*/

時間複雜度爲O（| A | + | B |）在最壞的情況下，其中| A | & | B |是分別存在於陣列A和B中的元素的數量。因此，你會得到線性複雜性。

來源

2015-10-16 17:43:16

如何檢查一個數組是否是另一個數組的子序列？

回答

相關問題