DSA 问题集第三章

发表于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟

Typora 自动上传图片把我顺序全弄乱了，索性重做了一个。
纯浪费时间来的。

牧濑红莉栖

列表

image-20260416164407091

如果前后次序未知，可以固定一个指针，另一个指针同时向前向后走，同时统计两个距离，谁先遇到另一个指针就输出那个距离。

image-20260416165351858
先跑到区间右端点，从右往左 p = p->pred 拷贝。空间性能基本不变，时间渐进依然 O (n) 但是常数变大。

1
2
3
4
5
0001 template <typename T> //依据蓝本列表的区间，复制出当前列表
0002 void List<T>::copy( LNP<T> p, Rank n ) {
0003    for ( init(); n--; p = p->succ ) //先创建空表；再将蓝本区间内各节点
0004       insertLast( p->data ); //依次复制，并作为末节点插入
0005 } //时间复杂度线性正比于n，以及每个T类型对象的深复制所需的时间

image-20260416165557016

设置两个指针 p = head,q = head->succ。p,q 同步移动，每次删除 p，p = q,q = q->succ，直到抵达 tail

image-20260416170119526

1
2
3
4
5
6
0001 template <typename T> //在无序列表区间(h,t)内，找到等于e的最靠前者：h < t
0002 LNP<T> List<T>::find( LNP<T> h, const T& e, LNP<T> t ) const {
0003    T bak = t->data; t->data = e; //预置哨兵
0004    while ( e != ( h = h->succ )->data ); //自前向后，逐个比对
0005    t->data = bak;  return h == t ? nullptr : h; //哨兵复原，返回终止位置
0006 } //find：O(n)
1
2
3
4
5
0001 template <typename T> void List<T>::dedup() { //O(n^2)
0002    for ( LNP<T> p = first(); p != tail; p = p->succ ) //在无重的前缀(head,p)中
0003       if ( LNP<T> q = find( head, p->data, p ) ) //查找可能与p相等的q
0004          remove(q); //若q确实存在，则（在常数时间内）删除之
0005 } //dedup

a) 最好情况全等，每次循环都要以 O (1) 时间找到前面的重复元素（因为就是第一个），O (1) 删除前一个相同的元素，循环 n 次 O (n)

b) 因为删除操作不会产生移动

c) 刚开始循环就会被预设哨兵拦下

d) 这个算法不变性在于维护了无重复元素的前缀。改成维护无重复后缀，需要从尾部实质节点开始，找区间 (p,tail) 里面的和当前相同的元素。

e) 需要手动调整指针位置，如果要删除 p 的时候备份 p->succ 再删除 p，然后跳转到原先的 p->succ；否则跳转 succ

f) 空表，单表，全重复，全不重复，重复在表头 / 尾，交错重复

image-20260416172900413

1
2
3
4
5
6
7
void operator()(T& data) {
    // 如果数据匹配，且还没找到过（这里实现为寻找第一个匹配项）
    if (data == target && !match) {
        match = current; 
    }
    current = current->succ;
}
1
2
3
4
5
6
7
void operator()(T& data) {
    // 因为是有序列表，只要当前数据 <= 目标值，就一直更新 match
    if (data <= target) {
        match = current;
    }
    current = current->succ;
}

image-20260416192323242

1
2
3
4
5
6
0001 template <typename T> void List<T>::uniquify() { //成批剔除重复元素，效率更高
0002    if ( _size < 2 ) return; //过短的列表，自然不含相等元素
0003    for ( LNP<T> p = first(), q = p->succ; q != tail; q = p->succ )
0004       if ( p->data != q->data ) p = q; //若p与其后继q不等，则前进一步
0005       else remove( q ); //否则直接删除后者，而不必如向量那样间接删除
0006 } //uniquify()

a) 节省多余操作

b) 只用一个指针，每次判断这个指针和它的后继是否相同，相同就删后继不相同就不删。

image-20260416194310494

1
2
3
4
5
6
7
0001 template <typename T> LNP<T> List<T>::getMax( LNP<T> h, LNP<T> t ) { //2 <= t - h
0002    LNP<T> m = t->pred; //当前的最大者
0003    for ( t = m->pred; h != t; t = t->pred ) //从后向前，逐个比较
0004       if ( m->data < t->data ) //见贤：若发现严格更大的元素
0005          m = t; //思齐：则更新记录
0006    return m; //最终的最大者：即便有多个，也总是取最靠后者
0007 } //getMax：O(n)
1
2
3
4
5
0001 template <typename T> void List<T>::selectionSort( LNP<T> h, LNP<T> t ) {
0002    for ( LNP<T> x = t->pred; h->succ != x; t = x, x = t->pred ) //反复地从无序前缀(h,t)中
0003       swap( getMax(h,t)->data, x->data ); //找出最大者，并通过交换令其就位
0004       //getMax(h,t)->movePred(t); //亦可通过移动就位：同样是O(1)成本，且也能免除new与delete
0005 }

c) 修改 < 为 <=

d) n-1 次，完全相同的列表每次在后面遇到相同元素需要更新 x

选择排序

image-20260416195635621 image-20260416195707829 image-20260416195716764

a) m 指向的位置是无序前缀的末尾，所以 m 和 x 同属一个轮换且相邻

b) m 显然，原先指向 m 所在位置的元素现在指向位置不变，但是指向了 x，而 x 指向下一个元素，相当于跳过了 m，所以当前轮换所缩减一个单位。

c) 对于长度为 L 的环，需要交换 L-1 才能让所有人都就位，此时最后一个人一定在正确的位置上，这就会产生多余的交换。所以 k 个环恰好对应 k 个多余交换。

d)e)ppt

f) 多余交换次数 = 轮换的个数

image-20260416200725115

c) 错。[3,2,1] 一共只有一次原地移动但是两个环

e) 对。在前 r 个元素中把最大的抽走，剩下的相对位置不变，也就是说不改变随机性。依然调和级数求和。

插入排序

始终维护前缀 S 有序。反复针对 e = A [r]，在 S 中查找适当位置插入 e。

哨兵可以支持头插尾插，不需要多余补丁代码。

1
2
3
4
0001 template <typename T> void List<T>::insertionSort( LNP<T> h, LNP<T> t ) {
0002    for ( LNP<T> r = h->succ, s = r->succ; r != t; r = s, s = r->succ ) //反复在有序前缀(h,r)
0003       r->moveSucc( search( h, r->data, r ) ); //内找到不大于[r]的最靠后者，并将[r]移至紧邻其后
0004 } //insertionSort

对输入敏感，最好 O (n)（每次 search 都是直接遇到比自己小的人），最坏 O (n2) 的在线算法

image-20260416204831001

a)1/n!

b) 依然不改变局部随机性，调和级数之和 ln (n)

c) 处理第 k 个元素的时候，前 k-1 个元素已经有序，平均来看需要查找跳跃 k / 2 次，高斯和。

$\frac {n (n + 1)}{4}$ 依然 O (n2)

便于统计，把逆序对算作后者的。

image-20260416205714000

在插入排序中把未排序的元素 e 插入前缀中，需要从右往左挨个和前面的元素比对大小，只要前面的元素比自己大就往前走，比对次数就是 e 的逆序对

于是运行时间是 O (n + I)，n 是必须付出的、所有元素都访问一遍花费的时间，I 是总的逆序对数量。

image-20260416210429143

b) 一共有 $C^2_n$ 对，每一对成为逆序对的可能都是 1 / 2，因为数学期望似乎具有线性性质所以就是 $\frac {n (n + 1)}{4}$ 对

归并排序

二路归并

1
2
3
4
5
6
7
8
0001 template <typename T> //归并：(h,y) + [y,t)
0002 void List<T>::merge( LNP<T> h, LNP<T> y, LNP<T> t ) {
0003    for ( LNP<T> x = h->succ; (x != y) && (y != t); )
0004       if ( x->data > y->data ) //小者优先；相等时x优先，以保证稳定性
0005          (y = y->succ)->pred->movePred(x);
0006       else
0007          x = x->succ;
0008 } //O(n+m)

image-20260416213523987

c)$T(n)=T(\lambda n)+T((1-\lambda)n)+O(n),T(n)=O(nlogn)$

d) 插入排序