我期待探索不同的算法,遞歸和動態編程,檢查如果一個arrayA是arrayB的子序列。例如,如何檢查一個數組是否是另一個數組的子序列?
arrayA = [1, 2, 3]
arrayB = [5, 6, 1, 7, 2, 9, 3]
thus, arrayA is indeed a subsequence of arrayB.
我已經嘗試了幾種不同的搜索,但我似乎找到是算法計算最長遞增子。
我期待探索不同的算法,遞歸和動態編程,檢查如果一個arrayA是arrayB的子序列。例如,如何檢查一個數組是否是另一個數組的子序列?
arrayA = [1, 2, 3]
arrayB = [5, 6, 1, 7, 2, 9, 3]
thus, arrayA is indeed a subsequence of arrayB.
我已經嘗試了幾種不同的搜索,但我似乎找到是算法計算最長遞增子。
既然你必須匹配的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;
}
這是一個聰明的解決方案,但有什麼方法可以通過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
中的元素的數量。因此,你會得到線性複雜性。
您需要高效的解決方案嗎? – svs
@svs是的效率在這裏很重要。 –
因此,在'arrayB'中查找的元素總是與'arrayA'的順序相同? – Sylwester