使運行時複雜度更短（C++）

Question

由於內部有兩個嵌套的重複循環，remove_dup函數的運行時複雜度爲O（n^2）。我的任務是獲得與O（n）相同的結果。
我真的不知道如何可能看起來像。

int add_without_dup (char x, vector<char>& r) 
{// pre-condition: 
    assert (true) ; 
// post-condition: x is added to the end of r if it is not yet present in r 
//     the result is the number of comparisons performed in this function 
int i = 0 ; 
while (i < size(r) && r[i] != x) 
    i++ ; 
if (i == size(r)) 
    r.push_back (x) ; 
return i ; 
} 


int remove_dup (vector<char>& source, vector<char>& dest) 

{// pre-condition: 
assert (size (dest) == 0) ; 
// post-condition: dest is a copy of source without duplicate elements 
//     the result is the number of comparisons performed in this function 
int nr_of_comparisons = 0 ; 
for (int i = 0 ; i < size (source) ; i++) 
    nr_of_comparisons += add_without_dup (source[i], dest) ; 
return nr_of_comparisons ; 
} 

Answer 1

因爲你的字符只能有256個可能的值，你可以保留一個bool array[256]。當你插入一些東西時，將值設置爲true。當你想檢查它是否在你身上檢查值是否設置爲true。

複雜度是O(N + S)其中S是你想要在你的向量中可能的值的數量。通常，對於char，N >> S，所以S無關緊要。