Question

数据结构

2.假设递增有序顺序表A、B分别表示一个集合，设计算法以判断集合A是否是集合B的子集，并要求时间尽可能少。
3.设计算法将递增有序顺序表A、B中的元素值合并为一个递增有序顺序表C，并要求时间尽可能少。

Answer 1

2. 思想，本质是判断A中所有的元素都在B中出现。
不过由于A、B都是有序的，所以：
假设A(m) = B(n)，则所有B(i,i<n) < A(m+1)，即不用再判断之前的B中的元素
假设A(m) < B(n)，则所有B(j,j>n) > A(m)，即不用再判断之后的B中的元素
所以，算法为：

1) 假设A有元素m个，B有元素n个，m<=n（不然A肯定不是B的子集）
2) 设i=0; 对j=0到n进行循环
2.1) 如果A(i) < B(j) 则退出循环，报错，A不是B的子集
2.2) 如果A(i) == B(j) 则i++，如果i>=m，即遍历了所有的A，则退出循环
2.3) 继续循环
3) 如果i<>m，即没有遍历所有的A，则报错，A不是B的子集
算法时间最多为O(n)

2. 思想其实与上面差不多，依次从A、B中取最小的，放入结果集合C：
1) 假设A有元素m个，B有元素n个，结果集合为C
2) 设i=0; j=0，开始循环，直到i>=m and j>=n
2.1) 如果j>=n or A(i)<B(j) 则C(i+j)=A(i), i++，继续循环
2.2) 不然C(i+j)=B(j), j++，继续循环

算法时间为 O(m+n)