数据结构（1）：顺序表（下）

上一回，我讲了一下顺序表的定义和基本操作的实现；这一会我们来看一下顺序表相关的 4 道比较典型的算法题。这里我不再选择 C/C++来实现算法，而是选择 Python。

第 1 题

问题

设将 n（n＞1）个整数存放到一维数组 R 中。设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移 p（0＜p＜n）个位置，即将 R 中的数据由

解答

算法的基本设计思想：可将这个问题视为把数组 ab 转换成数组 ba（a 代表数组的前 p 个元素，b 代表数组中余下的 n-p 个元素），先将 a 逆置得到

设 reverse 函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3（p=3）个位置的过程如下：

reverse(0,p-1) 得到 cbadefgh；

reverse(p,n-1) 得到 cbahgfed；

reverse(0,n-1) 得到 defghabc。

注：reverse 中，两个参数分别表示数组中待转换元素的始末位置。

使用 Python 描述算法如下：

def reverse(r, fro, to):    for i in range((to-fro+1)//2):        r[fro+i], r[to-i] = r[to-i], r[fro+i]

def converse(r, p):    n = len(r)    reverse(r, 0, p-1)    reverse(r, p, n-1)    reverse(r, 0, n-1)

上述算法中三个 reverse 函数的时间复杂度分别为 O(p/2)、O((n-p)/2) 和 O(n/2)，故所设计算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

第 2 题

问题

一个长度为 L（L≥1）的升序序列 S，处在第

现在有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。

解答

算法的基本设计思想：分别求两个升序序列 A 和 B 的中位数，设为 a 和 b，求序列 A、B 的中位数过程如下：

1. 若 a=b，则 a 或 b 即为所求中位数，算法结束。
2. 若 a＜b，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半，要求两次舍弃的长度相等。
3. 若 a＞b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求两次舍弃的长度相等。

在保留的两个升序序列中，重复过程1、2、3，直到两个序列中均只含一个元素时为止。较小者即为所求的中位数。

代码如下：

def m_search(a, b):    n = len(a)    s1, d1, m1, s2, d2, m2 = 0, n-1, 0, 0, n-1, 0    # 分别表示序列 a 和 b 的首位数，末位数和中位数    while s1 != d1 or s2 != d2:        m1, m2 = (s1+d1)//2, (s2+d2)//2        if a[m1] == b[m2]:            return a[m1]        if a[m1] < b[m2]:            if (s1+d1) % 2 == 0:  # 若元素个数为奇数                s1 = m1  # 舍弃 a 中间点以前的部分且保留中间点                d2 = m2  # 舍弃 b 中间点以后的部分且保留中间点            else:  # 元素个数为偶数                s1 = m1+1  # 舍弃 a 中间点及中间点以前部分                d2 = m2  # 舍弃 b 中间点以后部分且保留中间点        else:            if (s2+d2) % 2 == 0:  # 若元素个数为奇数                d1 = m1  # 舍弃 a 中间点以后的部分且保留中间点                s2 = m2  # 舍弃 b 中间点以前的部分且保留中间点            else:  # 元素个数为偶数                d1 = m1  # 舍弃 a 中间点以后的部分且保留中间点                s2 = m2+1  # 舍弃 b 中间点及中间点以前的部分    return a[s1]if a[s1] < b[s2]else b[s2]

算法的时间复杂度为 O(log₂n)，空间复杂度为 O(1)。

第 3 题

问题

已知一个整数序列

则称 x 为 A 的主元素。例如 A=(0, 5, 5, 3, 5, 7, 5, 5)，则 5 为主元素；又如 A=(0, 5, 5, 3, 5, 1, 5, 7)，则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A 中的主元素。若存在主元素，则输出该元素；否则输出 -1。

解答

给出算法的基本设计思想：算法的策略是从前向后扫描主元素，标记一个可能成为主元素的元素 Num。然后重新计数，确认 Num 是否是主元素。

算法可分为以下两步：

1. 选取候选主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1，否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
2. 判断 c 中元素是否是真正的主元素。再次扫描该数组，统计 c 中元素出现的次数，若大于 n/2，则为主元素；否则。序列中不存在主元素。

算法实现如下：

def majority(a):    n = len(a)    c, count = a[0], 1  # c 用来保存候选主元素，count 用来计数。设置 a[0] 为候选主元素    for i in range(n):  # 查找候选主元素        if a[i] == c:            count += 1  # 对 a 中的候选主元素计数        else:  # 处理不是候选主元素的情况            if count > 0:                count -= 1            else:  # 更换候选主元素，重新计数                c, count = a[i], 1    if count > 0:        count = 0        for i in range(n):  # 统计候选主元素的实际出现次数            if a[i] == c:                count += 1    if count > n/2:  # 确认候选主元素        return c    return-1  # 不存在主元素

实现的程序的时间复杂度为 O(n)，空间复杂度为 O(1)。

第 4 题

问题

给定一个含 n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 {-5,3,5,3} 中未出现的最小正整数是 1；数组 {1,2,3} 未出现的最小正整数是 4。

解答

要求时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组 B[n]，用来记录 A 中是否出现了 1~n 中的正整数，B[0] 对应正整数 1，B[n-1] 对应正整数 n，初始化 B 中全部为 0。由于 A 中含有 n 个整数，因此可能返回的值是 1~n+1，当 A 中 n 个数恰好为 1~n 时返回 n+1。当数组 A 中出现小于等于 0 或大于 n 的值时，会导致 1~n 中出现空余位置，返回结果必然在 1~n 中，因此对 A 中出现了小于等于 0 或大于 n 的值可以不采取任何操作。

经过以上分析可以得出算法流程：从 A[0] 开始遍历 A，若 0＜A[i]≤n，则令 B[A[i]-1]=1；否则不做操作。对 A 遍历结束后，开始遍历数组 B，若能查找到第一个满足 B[i]==0 的下标 i，返回 i+1 即为结果，此时说明 A 中未出现的最小正整数在 1~n 之间。若 B[i] 全部不为 0，返回 n+1。

算法实现：

def find_miss_min(a):    n = len(a)    b = [0] * n  # 标记数组。赋初值为 0    for i in range(n):        if 0 < a[i] <= n:  # 若 a[i] 的值介于 1~n，则标记数组 b            b[a[i]-1] = 1    for i in range(n):  # 扫描数组 b，找到目标值        if b[i] == 0:            return i+1    return n+1

时间复杂度：遍历 A 一次，遍历 B 一次，两次循环内操作步骤为 O(1) 量级，因此时间复杂度为 O(n)。空间复杂度：额外分配了 B[n]，空间复杂度为 O(n)。

总结

最后，我们可以发现顺序表在靠近表头的位置增加或者删除元素需要大量的移动元素，预知如何避免，请看下回

‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍