版本号标记

这是一个处理需要反复标记的问题的一个小技巧，以一个ACM形式的题目为例： 输入：第一行是一个数字N，表示N个case，之后每个case第一行是一个数字M，表示这个case有M个数字输入，接下来是M个数字，每个数字范围是0<=n<K 输出：对每个case，输出M个数字去重后的数量

当然，这题本身没什么难度，弄个hash_set就行了，不过为了说明问题，我们假定做题的人比较笨，使用bitmap：

bm = BitMap(K)   
N = read_int()   
for i from 1 to N:   
    M = read_int()   
    for j from 1 to M:   
        bm.set(read_int())   
    count = 0   
    for k from 0 to K-1:   
        if bm.is_set(k):   
            count += 1   
            bm.unset(k)   
    print count

构造一个bitmap，对于每个case，设置对应的位，最后统计数量，这里借鉴了上一篇中的做法，统计的时候顺便unset，就省去了初始化，空间和时间复杂度都是O(K)，指数级的，所以说这是一个比较笨的算法（为何是指数级，后面再说）

换一种思路，对于每个case的M个数字，如果每次read_int后判断下是否已在位图，则可以实时统计count，修改j的循环为：

bm.reset()   
count = 0   
for j from 1 to M:   
    num = read_int()   
    if bm.is_set(num):   
        continue   
    count += 1   
    bm.set(num)

不过这并没什么改善，虽然后面k的循环省了，bm.reset()依然要遍历

由于bitmap中每个元素只有0和1两种状态，每个case是独立的，因此每次要初始化（上述两种方案只是初始化方式不同），如果将状态扩展为多个，就能避免反复初始化：

tag = new int[K]; //假设自动初始化为全0   
N = read_int()   
for i from 1 to N:   
    M = read_int()   
    count = 0   
    for j from 1 to M:   
        num = read_int()   
        if tag[num] == i:   
            continue   
        count += 1   
        tag[num] = i   
    print count

用一个整数数组tag代替bitmap，初始化为0，对于第i个case，用i来标记num，这样一来每个case虽然公用tag，但各自标记方法不同，就不用初始化了，不考虑tag的建立，就单个case来说，时间复杂度是O(M)

于是，对于上篇末尾说的延迟清除，如果将marked和unmarked两种状态标记做一下改动，就可以区分已标记、待回收和新对象，而且省却了全局初始化，代价就是垃圾收集器自己维护一个递增的版本管理。不过，实际使用的算法不一定是这么写的