有序向量的唯一化和无序向量不同, 分为低效版和高效版. 低效版代码如下:
- template
- <typename
- T
- > int Vector<T>::uniquify() {
- int oldSize = _size;
- int i = 1;
- while (i <_size) {
- _elem[i - 1] == _elem[i] ? remove(i) : i++;
- }
- return oldSize - _size;
- }
该算法的正确性在于有序算法中的重复元素必然是紧邻的, 所以只要自前向后逐个扫描再使用 remove() 接口删除靠后者, 否则转向下一个元素, 如此即可实现有序向量的唯一化.
这种算法的时间消耗主要来自于 while 循环, 迭代次数是 n-1 次, 且在最坏情况下每次循环都需要执行一次 remove 操作, 所以共计有:
(n-2) + (n-3) + (n-4) +...+2 + 1 = O(n*n)
由此可见, 效率竟然和无序元素相同, 所以十分低下, 原因在于, 在对 remove() 接口的调用过程中, 同意元素作为后继元素向前多次移动, 且每次只移动一个单元. 这是因为每次进行 remove() 操作的时候, 我们只会进行一对一的独立删除. 所以倘若我们成批的删除重复元素必将大大提高效率.
由此给出高效版的代码如下:
- template
- <
- typename
- T
- > int Vector<T>::uniquify() {
- Rank i = 0, j = 0;
- while (++j < _size) {
- if (_elem[i] != _elem[j]) {
- _elem[++i] = _elem[j];// 发现不同元素时, 向前移至紧邻于前者右侧
- }
- _size = ++i; shrink();// 直接截除尾部多余元素
- }
- return j - i;
- }
这份算法的 while 循环的每次迭代只需要进行一次比较, 向后移动一到两个位置指针, 并至多向前复制一个元素, 故一次迭代只需要常数时间, 总体只需要 O(n) 的时间.
来源: http://www.bubuko.com/infodetail-2660172.html