线性表P19综合题(2)
L如果你害怕失敗，那你很有可能會失敗。 If you’re afraid to fail, then you’re probably going to fail.
线性表P19综合题(2)
从此篇开始，不再放出main函数和其他辅助函数，例如swap，debug。
09
给定 三个序列A、B、C，长度均为n ，且均为无重复元素的递增序列，请设计一个时间 上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素 。例如，数组A为 {1 , 2 , 3 ]， 数 组 B 为 {2 , 3 ， 4 ]， 数 组 C 为 {- 1 , 0 . 2 }， 则 输 出 2 。 要 求 :
1 )给出算法的基本设计思想。
2 )根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
3 )说明你的算法的时间复杂度和空间复杂度。
答案1 暴力法 直接bubble
List mergeAll(List A,List B,List C){
List All;
All.length=A.length+B.length+C.length;
for(int i=0;i<A.length;i++){//长度都是n，所以一个for直接合并。
All.data[i]=A.data[i];
All.data[i+A.length]=B.data[i];
All.data[i+A.length+B.length]=C.data[i];
}
for(int i=0;i<All.length-1;i++){ //冒泡，O(n^2)
for(int j=i+1;j<All.length;j++){
if(All.data[i]>All.data[j]){
swap(All.data[i],All.data[j]);
}
}
}//bubble
return All;
}答案2 三指针算法 O(m+n+l)
List MergeList(List l1,List l2,List l3){
List all;
all.length=l1.length+l2.length+l3.length;
int i=0,j=0,l=0;
int k=0;
while(i<l1.length && j<l2.length && l<l3.length){
if(l1.data[i]<=l2.data[j] && l1.data[i]<=l3.data[l]){ //这里要不严格小于 用小于要加else
all.data[k++]=l1.data[i++];
}
else if(l2.data[j]<=l1.data[i] && l2.data[j]<=l3.data[l]){
all.data[k++]=l2.data[j++];
}
else if(l3.data[l]<=l1.data[i] && l3.data[l]<=l2.data[j]){
all.data[k++]=l3.data[l++];
}
}
while(i<l1.length && j<l2.length){ //处理l1 和 l2
if(l1.data[i]<l2.data[j]){ //这里严不严格都可以
all.data[k++]=l1.data[i++];
}
else{
all.data[k++]=l2.data[j++];
}
}
while(i<l1.length && l<l3.length){ //l1 l3
if(l1.data[i]<l3.data[l]){
all.data[k++]=l1.data[i++];
}
else{
all.data[k++]=l3.data[l++];
}
}
while(j<l2.length && l<l3.length){//l2 l3
if(l2.data[j]<l3.data[l]){
all.data[k++]=l2.data[j++];
}
else{
all.data[k++]=l3.data[l++];
}
}
while(i<l1.length) all.data[k++]=l1.data[i++]; //处理剩余
while(j<l2.length) all.data[k++]=l2.data[j++];
while(l<l3.length) all.data[k++]=l3.data[l++];
return all;
}答案3 双指针 分批合并
代码更少一点，复杂度一样O(m+n+l)
List MergeList2(List l1,List l2){
List all;
all.length=l1.length+l2.length;
int i=0,j=0,k=0;
while(i<l1.length && j<l2.length){
if(l1.data[i]<l2.data[j]) all.data[k++]=l1.data[i++];
else all.data[k++]=l2.data[j++];
}
while(i<l1.length) all.data[k++]=l1.data[i++];
while(j<l2.length) all.data[k++]=l2.data[j++];
return all;
}
List Function(List l1,List l2,List l3){
return MergeList2(l3,MergeList2(l1,l2));
}10
【 2 0 1 0 统 考 真 题 】 设 将 n ( n > 1 ) 个 整 数 存 放 到 一 维 数 组 R 中 。设 计 一 个 在 时 间 和 空 间 两 方 面 都 尽 可 能 高 效 的 算法 。 将 R 中 保 存 的 序 列 循 环 左 移 p (0 < P < n )个 位 置 ，即 将 R 中 的 数 据 由 (X o , X I ， ， X n - 1 )变 换 为 (X p X p + 1 " ， X n - 1 , X o , M I ，: ，X p - 1 )。 要 求 : 1)给出算法的基本设计思想。 2 )根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。 3 )说明你所设计算法的时间复杂度和空间复杂度。
void swapmn(List& list,int m,int n){
List temp;
temp.length=list.length;
for(int i=0;i<=m-1;i++){
temp.data[n+i]=list.data[i];
}
for(int i=m;i<=m+n-1;i++){
temp.data[i-m]=list.data[i];
}
list=temp;
}直接当成p和n-p置换。
11
【2011统考真题】一个长度为L(L≥1)的升序序列S，处在第「L/21个位置的数称为S 的 中 位 数 。 例 如 ， 若 序 列 S ，= (1 1 , 1 3 , 1 5 , 1 7 . 1 9 )， 则 S ;的 中 位 数 是 1 5 ， 两 个 序 列 的 中 位 数 是 含 它 们 所 有 元 素 的 升 序 序 列 的 中 位 数 。 例 如 ， 若 S : = ( 2 , 4 , 6 , 8 , 2 0 )， 则 S I 和 S 的 中 位数是11 。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能 高效的算法，找出两个序列A 和B 的中位数。要求: 1)给出算法的基本设计思想。 2 )根据设计思想，采用C或C++或Java 语言描述算法，关键之处给出注释。 3 )说明你所设计算法的时间复杂度和空间复杂度。
答案1 暴力合并排序（bubble)
ElemType findMid(List l1,List l2){
List l3;
l3.length=l1.length+l2.length;
for(int i=0;i<l1.length;i++){
l3.data[i]=l1.data[i];
//l3.data[i+l1.length]=l2.data[i];
}
for(int i=0;i<l2.length;i++){
l3.data[i+l1.length]=l2.data[i];
}
//debug(l3);
for(int i=0;i<l3.length-1;i++){ //bubble
for(int j=i+1;j<l3.length;j++){
if(l3.data[i]>l3.data[j]){
swap(l3.data[i],l3.data[j]);
}
}
}
//debug(l3);
int mid=(1.0*l3.length)/2+0.5;//向上取整 mid的小数点数字只可能是0.5
return l3.data[mid];
}答案2 双指针归并O(m+n)
ElemType MergeFindMid(List l1,List l2){
List l3;
l3.length=l1.length+l2.length;
int i=0,j=0,k=0;
while(i<l1.length || j<l2.length){
if(l1.data[i]<l2.data[j]){
l3.data[k++]=l1.data[i++];
}
else{
l3.data[k++]=l2.data[j++];
}
}
while(i<l1.length) l3.data[k++]=l1.data[i++];
while(j<l2.length) l3.data[k++]=l2.data[j++];
int mid=(1.0*l3.length)/2+0.5;//向上取整 mid的小数点数字只可能是0.5
return l3.data[mid];
}12
【2013统考真题】已知一个整数序列A=(Q0,al，“ ，Qp-1)，其中O≤a，<n(O≤i<n)。若 存 在 a p l = a p 2 = = Q p m = X 且 m > n / 2 ( 0 ≤ P k < N , 1 ≤ K ≤ m )， 则 称 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。要求:
1)给出算法的基本设计思想。 2 )根据设计思想，采用 C或 C++或J ava 语言描述算法，关键之处给出注释。 3 )说明你所设计算法的时间复杂度和空间复杂度。
答案1 双循环遍历找重复值
ElemType findX(List list){
ElemType oldnum=0;
ElemType num;
int old=1;
int tol=1;
for(int i=0;i<list.length-1;i++){
for(int j=i+1;j<list.length;j++){
if(list.data[i]==list.data[j]){
num=list.data[i];
tol++;
}
}
if(old<tol) {
old=tol;
oldnum=num;
}
tol=1;
}
if(old>list.length/2) return oldnum;
else return -1;
}答案2 排序后 线性扫描 （快速排序）O(nlogn)
int part(int *arr, int l, int r) {
int i=l,j=r+1;
int v=arr[l];
while(1){
while(arr[++i]<v) if(i==r) break;
while(arr[--j]>v) if(j==l) break;
if(i>=j) break;
int t;
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
int t;
t=arr[l];
arr[l]=arr[j];
arr[j]=t;
return j;//切分位置 就是中心位置
}
void Quick(int *arr, int l,int r) {
if(l>=r)
return;
int j=part(arr,l,r);
Quick(arr,l,j-1);
Quick(arr,j+1,r);
}
//排序后 线性扫描
//复杂度取决于排序的复杂度
ElemType findX2(List list){
Quick(list.data,0,list.length);
debug(list);
int i=0,j=1;
int len=1;
ElemType num;
while(j<list.length){
if(list.data[i]==list.data[j]){
j++;
}
else {
if(j-i>len){
len=j-i;
num=list.data[i];
}
i=j++;
}
}
if(j==list.length && list.data[i]==list.data[j-1]){ //后面一直连续 特判一下
len=j-i;
num=list.data[i];
}
if(len>list.length/2) return num;
else return -1;
}答案3 哈希表 （暂无）
13
【2018 统考真题】给定一个含n (n≥1)个整数的数组，请设计一个在时间上尽可能高 效的算法，找出数组中未出现的最小正整数。例如，数组{- 5，3，2，3}中未出现的最小正 整数是1;数组{1，2, 3}中未出现的最小正整数是4。要求: 1 )给出算法的基本设计思想。 2 )根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。 3 )说明你所设计算法的时间复杂度和空间复杂度
答案1 排除所有不是正整数的数，桶排序。时间上O(n)
ElemType findMinZ(List list){ //正整数，直接桶排序
ElemType max=-1;
for(int i=0;i<list.length;i++){
if(list.data[i]>max) max=list.data[i];
}//找到最大值。
//给桶分配最大空间
List buket;
buket.length=max;
for(int i=0;i<=max;i++){
buket.data[i]=0;
}
for(int i=0;i<list.length;i++){
if(list.data[i]<=0) continue;
buket.data[list.data[i]]++;
}
for(int i=1;i<=max;i++){
if(buket.data[i]==0) return i;
}
return max+1;
}14
【 2 0 2 0 统 考 真 题 】 定 义 三 元 组 ( a , b , c )( a , b , c 均 为 整 数 ) 的 距 离 D = l a - 列 + | b - q + l e - a 。 给定3 个非空整数集合SI、S2和S3，按升序分别存储在3 个数组中。请设计一个尽可能 高 效 的 算 法 ， 计 算 并 输 出 所 有 可 能 的 三 元 组 (a . b , c ) ( a E S i , b E S , C E S s ) 中 的 最 小 距 离 。 例 如 S i = {- 1 , 0 . 9 }， S 2 = { - 2 5 ，- 1 0 . 1 0 , 1 1 }， S s = {2 . 9 , 1 7 , 3 0 , 4 1 }， 则 最 小 距 离 为 2 ， 相 应 的 三 元 组 为 (9 , 1 0 , 9 。 要 求 : 1)给出算法的基本设计思想。 2 )根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。 3 )说明你所设计算法的时间 复杂度和空间复杂度。
暴力O(n^3)
ElemType abs(ElemType a,ElemType b){
return (a-b>=0?a-b:b-a);
}
int getDistance(List s1,List s2,List s3){
int dis=abs(s1.data[0]-s2.data[0])+abs(s2.data[0]-s3.data[0])+abs(s3.data[0]-s1.data[0]);
for(int i=0;i<s1.length;i++){
for(int j=0;j<s2.length;j++){
for(int k=0;k<s3.length;k++){
int temp=abs(s1.data[i]-s2.data[j])+abs(s2.data[j]-s3.data[k])+abs(s3.data[k]-s1.data[i]);
if(dis>temp) dis=temp;
}
}
}
return dis;
}答案的写法 O(n)
int getD(List s1,List s2,List s3){
int i=0,j=0,k=0,D_min=0x7fffffff,D;
while(i<s1.length && j<s2.length && k<s3.length && D_min>0){
D=abs(s1.data[i]-s2.data[j])+abs(s2.data[j]-s3.data[k])+abs(s3.data[k]-s1.data[i]);
if(D<D_min) D_min=D;
if(xIs_min(s1.data[i],s2.data[j],s3.data[k])) i++;
else if(xIs_min(s2.data[j],s3.data[k],s1.data[i])) j++;
else k++;
}
return D_min;
}移动最小元素的指针是为了在有序数组中尽快找到更小的距离。具体原因如下：
- 距离公式和有序性： 距离 D=∣a−b∣+∣b−c∣+∣c−a∣D = |a - b| + |b - c| + |c - a|D=∣a−b∣+∣b−c∣+∣c−a∣ 包含了三个绝对值，这意味着当我们移动一个值时，应该尽量缩小其他值与其的差距。由于数组是有序的，通过移动当前最小值的指针，我们能有效缩小与其他两个值的距离。
- 尝试更接近的值： 在有序数组中，移动当前最小元素的指针能让下一个值比当前值大，可能更接近其他两个数组中的值，从而减少整体距离。具体来说：
- 如果我们当前最小的值是 aaa，即 a≤ba \leq ba≤b 且 a≤ca \leq ca≤c，那么我们希望增大 aaa 的值以更接近 bbb 和 ccc。
- 同理，如果最小值是 bbb，则希望增大 bbb 的值；如果是 ccc，则希望增大 ccc 的值。
- 局部优化： 每次移动最小值的指针，都相当于进行了一次局部的优化，使得三元组更接近一个较优解，逐步逼近全局最优解。
移动最大指针，只是效果不好，但是仍然可以使用。