DSA 问题集第二章

发表于 2026-04-16 分类于数据结构阅读次数：本文字数： 682 阅读时长 ≈ 2 分钟

好早之前做的现在拿来复习正好。

DSA 问题集第二章

a)，n=$c^{k$,总成本 $1 + c+…+c}{k-1}=\frac {n-1}{c-1}$ 均摊得 1/(c-1)

b)，常倍数越大时间复杂度越低

c)，常倍数越大空闲空间越大，空间浪费多

e)，每次扩容到 max {n + m,n * c}，依然 O (1)

均摊是整个操作序列的平均，不是特定的平均。一次昂贵的操作换来了许多次便宜的操作

c)：因为 expand 的装填因子是 1/2，如果一样的话，在 1/2 处反复做删除插入会造成大量扩容缩容。

template <typename T> //0 <= lo < hi <= _size
Rank Vector<T>::find( const T& e, Rank lo, Rank hi ) const { //O(hi-lo)
   T bak = _elem[hi]; _elem[hi] = e; //先将目标存入哨兵：因总有_size < _capa，故不致溢出
   while ( e != _elem[lo] ) lo++; //再从前向后，逐个比对
   _elem[hi] = bak; return lo; //哨兵还原；返回最靠前的命中者，或hi示意失败
} //find

template <typename T> void Vector<T>::dedup() { //更紧凑地实现向量去重
   for ( Rank k = 0, i; k < _size; ) { //自前向后逐个考查每个元素[k]——从k=1开始亦可
      for ( i = 0; _elem[i] != _elem[k]; i++ ); //直接查找（[k]天然就是哨兵）
      if ( i < k ) { //若存在相等的[i]，则删除之，(i,n)前移一个单位
         while ( ++i < _size )
            _elem[i-1] = _elem[i];
         _size--;
      } else //否则，直接转向下一元素
         k++;
   } //for
} //dedup: O(n^2)

a)：dedup () 将 elem [hi]=elem [k]，但是 hi 就等于 k 了

c)：直接内联

c)：对于 elem [k]，如果 find 到前面有 elem [i] 相同 (i + 1 次比对)，就 remove (n-1-i 次移动)，一共 n 次，n–；如果没找到一样的，就比对 k 次，k++。最后就是 1 + 2+…+n 次

d)：每次删除靠后的元素，因为 remove 操作复杂度和后缀长度相关

e)：

Rank i = 0; 
for (Rank j = 1; j < _size; j++) {
    // 在已去重的前缀 [0, i] 中查找 _elem[j]
    if (find(_elem[j], 0, i + 1) == i + 1) { // 如果没找到（返回值为越界位置）
        _elem[++i] = _elem[j]; // 将其加入唯一前缀中
    }
}
_size = i + 1; // 截断后续多余部分