邓俊辉<<数据结构>>-公开课-02-D1 发表于 2018-01-11 觉得markdown格式的页面, 排版很不舒服。虽然有标题的概念, 但是标题字体大小不容易分清, 结构不是显而易见。尝试使用不带格式的记笔记，仍然保留markdown语法, 以便复制对比效果。------------------------------ split line ---------------------------实现源码[dsacpp - vector_ordered](https://github.com/timtingwei/dsacpp/blob/master/src/02/vector_ordered.cpp)# 有序向量唯一化 无序: 比对 有序: 比较## 有序性及其甄别 > * 有序/无序序列中, 任意/总有一对相邻元素顺序/逆序。 > * 相邻逆序对数目, 可以度量逆序程度。 > * 逆序程度实现 ===================== source code ========================= // 逆序程度 /* my test code template <typename T> int Vector<T>::disordered() const { int count = 0; for (int i = 0; i < _size - 1; i++) if (_elem[i] != _elem[i+1]) count++; // ERROR: 逆序:前个元素大于后一元素 return count; } */ template <typename T> int Vector<T>::disordered() const { int count = 0; // 计数器 for (int i = i; i < _size; i++) count += (_elem[i-1] > _elem[i]); // 逆序对则计数+1, bool和int的隐式转换 return count; // 向量有序当且仅当n = 0 } // 若只需要判断是否有序, 首次遇到逆序对之后, 就立即终止 ============================================================ > * 若元素支持大小比较, 可将无序向量转换为有序向量。 > * 无序向量转换为有序向量后, 算法多可优化。## 低效算法 > 1, 我自己的低效deduplicate()版本, 依赖一次性remove函数. > * 尝试自己实现, ======================== sourece code ======================= // my deduplicate code // 唯一化(低效) int deduplicate_lower(int rm_arr[]); // 唯一化所依赖的通过索引数组一次性remove函数 void remove(int rm_arr[], int n); template <typename T> int Vector<T>::deduplicate_lower(int rm_arr[]) { // 删除有序向量重复的元素, rm_arr是保存删除对象索引数组, 返回被删除元素的数量 assert(!disordered()); // 当前为有序向量 Rank n = 0; // 数组当前插入位置 Rank r1 = 0, r2 = 1; // 创建两个索引值线性扫描 while (r2 < _size) { if (_elem[r1] == _elem[r2]) { // r2指向的元素和r1对应元素重复 rm_arr[n++] = r2; // 索引数组中加入r2 // remove(r2); } else { r1 = r2;} r2++; // 递增r2 } remove(rm_arr, n); // 一次性删除索引对应的元素 return n; // 返回删除元素数量 } // 有序向量唯一化所依赖的通过索引数组一次性remove函数 template <typename T> void Vector<T>::remove(int rm_arr[], int n) { // 删除索引除外的索引对应元素保留, 从左向右扫描 int i_n = 0; // 指向rm_arr中的元素 int new_i = 0; // 保留索引 T* old_elem = _elem; // 备份一份当前元素 _elem = new T[_capacity = _capacity]; for (int i = 0; i < _size; i++) { if (i != rm_arr[i_n]) { // 当前索引不在表中 _elem[new_i++] = old_elem[i]; // 当前索引对应元素赋值给当前元素的新位置 } else { // 当前索引在删除索引的表中 i_n++; // 指向下一个rm_arr中的元素 } } _size -= n; delete [] old_elem; } ============================================================= > 2, 视频中的唯一化(低效版) 代码如下: ======================= source code ======================== // 有序向量唯一化 template <typename T> int Vector<T>::uniquify() { int old_size = _size; int i = 0; // 首元素开始 while (i < _size - 1) { (_elem[i+1] == _elem[i]) ? remove(i+1) : i++; } // _size的改变由remove隐式完成 return old_size - _size; } ============================================================## 低效算法: 复杂度 > 1, 低效复杂度 运行时间取决于while循环, 总计 _size - 1 = n - 1 最坏情况: 每次调用remove(), 耗时O(n)~ O(1), 累计O(n^2) > 2, 比较 我实现了一次性remove的操作, 应该可以将O(n^2)的复杂度降到O(n)## 高效算法: > 1, 反思 低效来自于, 同一元素可作为删除元素的后继, 而多次参与前移。 > 2, 启示 将重复区间视为单位, 成批的删除 > 3, 算法 [i] [] [ . . . . duplicates] [j] 从i开始扫描, 直达找到不相等的元素j, 将j移动到i的后一位置。 高明之处在于: 实际上没有删除, 却等效于删除 ================== source code ============================== /* my test code template <typename> int Vector<T>::uniquify() { int old_size = _size; int i = 0, j = 1; // i指向首位置 int n = 1; // 实际更新后的_elem的索引 while (i < _size - 1) if (_elem[i] != _elem[j]) { _elem[n++] = _elem[j]; i = j; size--; } else {j++;} return old_size - n; } */ template <typename T> int Vector<T>::uniquify_faster() { int i = 0, j = 0; // 两个计数都指向首元素 while (++j < _size) { // j扫描到末尾 if (_elem[i] != _elem[j]) {_elem[++i] = _elem[j];} // j指向元素移到i后 } _size = ++i; shrunk(); // 改变_size数值后, 缩容 return j - i; // 注意j扫到尾端的特性 } // 依赖shrink(); ============================================================ /* 实现问题分析 // 为什么不要另外的n作为索引计数? 当j移动至i后, 计数i也增加, 重新指向移动位置后的j, 不需要对原有那份的拷贝即可完成索引操作。记录位置只用i。算法设计时，也考虑一个操作是否必要。一份复制是否必要。 // 为什么不在uniquify中进行new 和 delete? 接口分离的体现, 在函数中改变_size, 通过_size的改变, 再由shrunk/expand对空间进行操作。 */## 高效算法: 实例与复杂度 > 1, *反思 (典型例子) 共计n-1次迭代, 每次常数时间, 累计O(n)时间。 优化之处在于, 没有亦步亦趋的移动, 而是直接移动到最终的位置；又只通过计算得到_size规模, 没有任何显式的删除操作。 体现了, 一个差的算法, 在经过反思之后, 拟定的改进策略, 最终使得效率有所改进。