![](https://csdnimg.cn/release/download_crawler_static/86309695/bg8.jpg)
习题[2-11]~[2-12] 第2章 向量
[2-11] Vector::deduplicate()算法癿如下实现是否正确?为什么?
1 template <typename T> int Vector<T>::deduplicate() { //初除无序向量中重复元素(错诣版)
2 int oldSize = _size; //记弽原觃模
3 for (Rank i = 1; i < _size; i++) { //逐一考查_elem[i]
4 Rank j = find(_elem[i], 0, i); //在_elem[i]癿前驱中寺找不乀雷同者(至夗一个)
5 if (0 <= j) remove(j); //若存在,则初除乀(但在此种情冴,下一迭代丌必做i++)
6 }
7 return oldSize - _size; //向量觃模发化量,即被初除元素总数
8 }
【解答】
按照这一“算法”,若果真发现雷同的前驱_elem[j],虽然的确可以剔除之,但由此产生
的副作用是,秩为i的单元所对应的将不再是原先的_elem[i](而是其直接后继_elem[i + 1])。
这里即便假设,如教材代码2.14所实现的同名算法那样,仍能保证接受检查的每个_elem[i]
至多只有一个雷同的前驱,但因如上所述的副作用,原_elem[i + 1]也将被跳过,从而导致遗
漏与之雷同的元素。实际上,该“算法”每发现一次雷同,都有可能如此遗漏另一个雷同。
[2-12] 考查教材 42 页代码 2.14 中癿无序向量唯一化算法 deduplicate()。
a) 试证明,即便在最好情冴下,该算法也需要运行(n
2
)时间;
【解答】
该算法由O(n)次迭代构成,每次迭代都需要做一次查找操作,以及可能的一次删除操作。
对于元素_elem[k],若需做删除操作,则为此需花费O(n - k)时间移动所有的后继元素;反之,
若不需要做删除操作,则意味着此前的查找操作以失败告终,其间已经花费了O(k)时间。总而
言之,无论如何,各轮迭代至少需要(min(n - k, k))时间,累计(n
2
)。
b) 试参照教材 46 页代码 2.19 中有序向量唯一化算法 uniquify()癿技巧,改迕该算法,幵分枂其
时间复杂度;
【解答】
比如,在发现重复元素后不必立即剔除,而是借助位图Bitmap结构(习题[2-34])将其标
注为“待删除”。待所有雷同元素均已筛选完毕,再经一趟遍历在O(n)时间内统一删除。
经如此改进之后,尽管渐进的时间复杂度依然为O(n
2
),但因为时间消耗主要来源于静态的
查找操作,故实际的运行速度仍将大幅提高。
c) 试继续改迕该算法,使其时间复杂度降至 O(nlogn);
【解答】
最为直接的方法,就是先调用sort()接口对向量做整体排序,然后调用uniquify()接口做
唯一化处理。只要实现得当(比如采用教材所介绍的优化算法),这两步均只需O(nlogn)时间。
当然,由此将产生的一个副作用保留下来的元素,未必延续此前的相对排列次序。实际
上,完全可以在不增加渐进时间复杂度的前提下,消除这一副作用。请读者独立完成这一任务。