設計一種算法來查找兩個排序數字列表中的所有常見元素

Question

設計算法以查找兩個排序數字列表中的所有常見元素。例如。對於列表2,4,4，4,7和1,2,2,6,4,4,7，輸出應該是2,4,4,7您使用了哪種算法設計技術，爲什麼？你是什​​麼算法使得如果兩個給定的列表的長度是m和n分別

vector<int> findCommon(vector<int> arr1, vector<int>arr2){ 
vector<int> intersection; 
int n1 = arr1.size(); 
int n2 = arr2.size(); 
int k = 0, x = 0; 
while (x < n1 && k < n2) { 
if (arr1[x] > arr2[k]) { 
l++; 
} else if (arr2[k] > arr1[x]) { 
    k++; 
} else { 
    intersection.push_back(arr1[i]); 
    x++; 
    k++; 
} 
} 
return intersection; 

蠻力算法用作上述設計技術比較的最大和最小數。 複雜度爲O（m + n），因爲在最壞的情況下，兩個數組之間不會有交集，我們需要增加第一個索引總共m次，並增加第二個索引總共n次，這就是總共m + n次。

Answer 1

從兩個指向數組開頭的索引開始。如果這些索引指向的元素是相同的，那麼它是一個通用元素，並且我們推進這兩個指針。如果一個元素較小，則提前該指針（希望找到下一個相等的元素）。繼續下去，直到兩個指數中的任何一個達到結尾。

這是最有效的算法，因爲兩個列表已經排序。