有序性及其甄别
无序/有序
序列中,任意/总有
一对相邻元素顺序/逆序
因此,相邻逆序对的数目,可用以度量向量的逆序程度
template <typename T> // 返回逆序相邻元素对的总数
int Vector<T>::disordered() const {
int n = 0; // 计数器
for (int i = 1; i < _size; i__) // 逐一检查各对相邻元素
n += (_elem[i - 1] > _elem[i]); // 逆序则计数
return n; // 向量有序当且仅当 n = 0
} // 若只需判断是否有序,则首次遇到逆序对之后,即可立即终止
无序向量经预处理转换为有序向量之后,相关算法多可优化
元素去重(低效版)
观察:在有序向量中,重复的元素必然相互紧邻构成一个区间。因此,每一区间只需保留单个元素即可
template <typename T>
int Vector<T>::uniquify() {
int oldSize = _size; int i = 0; // 从首元素开始
while (i < _size - 1) // 从前向后,逐一比对各对相邻元素
(_elem[i] == _elem[i + 1]) ? remove(i + 1) : i++; // 若有雷同,则删除后者;否则,转至后一元素
return oldSize - _size; // 向量规模变化量,即删除元素总数
} // 注意:其中 _size 的减小,由 remove() 隐式完成
复杂度分析
运行时间主要取决于 while
循环,次数共计:_size - 1 = n - 1
最坏情况:每次都需调用 remove()
,耗时 O(n - 1) ~ O(1)
,累计 O(n^2)
尽管省去 find()
,总体竟与无序向量的 deduplicate()
相同
元素去重(高效版)
反思:低效的根源在于,同一元素可作为被删除元素的后继多次前移
启示:若能以重复区间为单位,成批删除雷同元素,性能必将改进
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; // 向量规模变化量,即被删除元素总数
} // 注意:通过 `remove(lo, hi)` 批量删除,依然不能达到高效率
实例与复杂度
本文由 OceanicKang 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Nov 25, 2018 at 04:12 pm