02 June 2016

对于两个集合都是未排序的 O(n*m)

for each a in set1 {
    for each b in set2 {
        if (a == b) {
            res.push(a);
        }
    }
}

对于两个集合是排好序的 O(log(n)*n) + O(log(m)*m) + O(n+m)

a = set1.pop();
b = set2.pop();

while ( !set1.empty() && !set2.empty()) {   // 两个集合都不为空
    if (a == b) {
        res.push(a)
    } else if (a < b) {                     // 如果集合 1 的当前元素比较小,集合 1 往后移动
        a = set1.pop();
    } else if (a > b) {                     // 如果集合 2 的当前元素比较小,集合 2 往后移动
        b = set2.pop();
    }
}