简单集合的差集求解

简单集合的差集求解

---

# 说明背景
最近，碰见一道小小的算法题，关于遍历搜索的，看似简单倒是门路倒是有几个。
所以，在此做一个小小总结与分享。如下：

# 题目描述
简单描述：现有两个字符集合a[m]，b[n]，且a[m]包含b[n]，即在集合b出现的字符同样也在集合a出现，所以m > n，最后求集合c[k]，即在集合a出现但是不存在b的元素的集合。

# 解法说明
1 蛮力法求解
     依次遍历集合a，b挑选择符合要求的元素，存放在集合c。对应时间复杂度为O(m * n).

2 较好的算法求解

     a 针对集合b排序，对应的时间复杂度为O(n * log（n))。

     b 依次遍历取集合a元素， 在集合b查找是否存在。对应的时间复杂度为O(m * log(n)）。

3 技巧的算法（高效）求解

     a 观察集合元素为字符，即char类型则数值范围[0, 255)，所以首先申请mark[256]作为标记, 初始为0 。

     b 遍历集合a一遍, 置mark[a[i]]为1 ， 对应的时间复杂度为O（m）。

     c 遍历集合b一遍, 置mark[b[i]]为2 ， 对应的时间复杂度为O（n）。

     d 遍历mark一遍，搜集元素值为1，存放于集合c，对应的时间复杂度为O（256）。

注：当m，n数值达到一定大小时候，解法3才能够体现出其明显的高效。

解法3，涉及C/C++代码实现，如下：

/// 时间复杂度 O (m + n + 256) -> O (N)

void select_diff_set1(vector<char>& all, vector<char>& part, vector<char>& diff_set)

{

    diff_set.clear();

    assert (all.size() >= part.size());

    char mark[256] = {0};

    memset(mark, 0, sizeof(mark));

    for (size_t i =0; i < all.size(); ++i)

        mark[(unsigned)all[i]] = 1;

    for (size_t i =0; i < part.size(); ++i)

        mark[(unsigned)part[i]] = 2;

    for (size_t i =0; i < sizeof(mark); ++i)

        if (1 == mark[i])

            diff_set.push_back(i);

    return;

}

# 附

代码示例参见：

https://github.com/huangjunkun/practice-for-programming/blob/master/test1/sub_unit.cpp

/// 时间复杂度 O (m + n + k) -> O (N)

void select_diff_set1(vector<char>& all, vector<char>& part, vector<char>& diff_set)

/// bad：时间复杂度 O (n(log(n) + m * log(n)) -> O (N*log(N))

void select_diff_set2(vector<char>& all, vector<char>& part, vector<char>& diff_set)

/// 蛮力法：时间复杂度 O (m * n) -> O (N^2)

void select_diff_set3(vector<char>& all, vector<char>& part, vector<char>& diff_set)