面接で出たクイズについてメモを残しておきます。
2つの配列があり、要素はソートされています。その積集合、つまり両方に含まれている要素を探してください。
何も考えずにやると二重ループのO(N^2)になりますが、ポインタを2つ用意して、値が等しければ積集合に追加。そうでないときは値が小さい方を1つ進める。計算量はO(N)といったところです。ソートされていなければソートするので、O(log N)になります。
vector<int> set_intersection( const vector<int> &set1, const vector<int> &set2 ) { int s1 = 0; int s2 = 0; vector<int> result; while( s1 != set1.size() && s2 != set2.size() ) { if( set1[s1] == set2[s2] ) { result.push_back(set1[s1]); s1++; s2++; } else if( set1[s1] < set2[s2]) { s2++; } else { s1++; } } return result; } int main() { vector<int> set1 = {1, 2, 4, 8, 16, 32}; vector<int> set2 = {1, 2, 3, 4, 5, 6}; auto set3 = set_intersection(set1, set2); for( auto a: set3 ) { cout << a << endl; } }
最近のコメント