目录

1、从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错误信息并退出运行。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=1e6+10;
const ll INF=2000000000;
const int mod=998244353;
#define MaxSize 50
typedef struct node{
    int data[MaxSize];
    int length;
}Sqlist;
void initsize(Sqlist &L,int a[],int n){
    for(int i=0;i<n;i++){
        L.data[i]=a[i];
    }
    L.length=n;
}
void print(Sqlist L){
    printf("%d\n",L.length);
    for(int i=0;i<L.length;i++){
        printf("%d ",L.data[i]);
    }
    printf("\n");
}
bool del_min(Sqlist &L,int &e){
    if(L.length<=0)return false;
    e=L.data[0];
    int flag=0;
    for(int i=1;i<L.length;i++){
        if(L.data[i]<e){
            flag=i;
        }
    }
    if(flag!=L.length-1){
        L.data[flag]=L.data[L.length-1];
    }
    L.length--;
    return true;
}
int main(){
    Sqlist L;
    int a[50],n=10;
    for(int i=0;i<n;i++){
        a[i]=rand()%10+1;
    }
    initsize(L,a,n);
    print(L);
    int e=-1;
    del_min(L,e);
    printf("%d\n",e);
    print(L);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

2、设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

void Reverse(Sqlist &L){
    int temp;
    for(int i=0;i<L.length/2;i++){
        temp=L.data[i];
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1]=temp;
    }
}
1
2
3
4
5
6
7
8

3、对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，删除线性表中所有值为x的数据元素。

bool deleteElem(Sqlist &L,int x){
    if(L.length<=0)return false;
    int k=0;
    for(int i=0;i<L.length;i++){
        if(L.data[i]!=x){
            L.data[k]=L.data[i];
            k++;
        }
    }
    L.length=k;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

4、从有序顺序表中删除其值在[s,t]之间的所有元素，若s或t不合理或顺序表为空，则显示出错误信息并退出运行。

bool deleteElem(Sqlist &L,int s,int t){
    if(L.length<=0)return false;
    if(s>=t)return false;
    int l=0;
    while(l<L.length&&L.data[l]<s)l++;
    int r=L.length-1;
    while(r>=0&&L.data[r]>t)r--;
    r++;
    for( ;r<L.length;r++,l++){
        L.data[l]=L.data[r];
    }
    L.length=l;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

bool deleteElem(Sqlist &L,int s,int t){
    if(L.length<=0)return false;
    if(s>=t)return false;
    int k=0;
    for(int i=0;i<L.length;i++){
        if(L.data[i]>=s&&L.data[i]<=t){
            k++;
        }else{
            L.data[i-k]=L.data[i];
        }
    }
    L.length-=k;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5、从顺序表中删除其值在给定值s与t之间（要求 s < t）的所有元素，若s或t不合理或顺序表为空，则显示出错误信息并退出运行。

暴力方法

bool deleteElem(Sqlist &L,int s,int t){
    if(L.length<=0)return false;
    if(s>=t)return false;
    int k=0;
    for(int i=0;i<L.length;i++){
        if(L.data[i]>=s&&L.data[i]<=t){
            k++;
        }else{
            L.data[i-k]=L.data[i];
        }
    }
    L.length-=k;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

双指针方法

bool deleteElem(Sqlist &L,int s,int t){
    if(L.length<=0)return false;
    if(s>=t)return false;
    int l=0,r=L.length-1;
    while(l<r){
        while(l<r&&(L.data[l]>t||L.data[l]<s))l++;
        while(l<r&&L.data[r]>=s&&L.data[r]<=t)r--;
        //cout<<l<<" "<<r<<endl;
        int temp=L.data[l];
        L.data[l]=L.data[r];
        L.data[r]=temp;
    }
    L.length=l;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6、从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

//有序表中删除所有值相同的元素(保留一个）
void Delete_Same(SqList &L)
{
    int i, j;
    for(i = 0, j = 1; j < L.length; j++)
    {
        if(L.data[i] != L.data[j])
            L.data[++i] = L.data[j];
    }
    L.length = i + 1;
}
1
2
3
4
5
6
7
8
9
10
11

7、将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

//将两个有序顺序表合并为一个有序顺序表
bool Merge(SqList A, SqList B, SqList &C)
{
    if(A.length + B.length > C.MaxSize)
        return false;
    int i = 0, j = 0, k = 0;
    for(i,j; i < A.length && j < B.length; i++, j++)
    {
        if(A.data[i] < B.data[j])
            C.data[k++] = A.data[i];
        else
            C.data[k++] = B.data[j]
    }
    while(i < A.length)
        C.data[k++] = A.data[i++];
    while(j < B.length)
        C.data[k++] = B.data[j++];
    C.length = k;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8、已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3~ am)和(b1,b2,b3~ bn)。编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3~ bn)放#在(a1,a2,a3~am)前面。

暴力结果

void change(int a[],int n,int p){
    int *b;
    b=(int *)malloc(sizeof(int)*n);
    memset(b,0,sizeof(b));
    for(int i=p;i<n;i++){
        b[i-p]=a[i];
    }
    for(int i=0;i<p;i++){
        b[n-p+i]=a[i];
    }
    for(int i=0;i<n;i++){
        a[i]=b[i];
    }
}
//调用接口：
change(a,n+m,m);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

优化结果

void Reverse(int a[],int left,int right){
    if(left>=right)return ;
    for(int i=0;i<(right-left+1)/2;i++){
        int temp=a[left+i];
        a[left+i]=a[right-i];
        a[right-i]=temp;
    }
    return ;
}
void converse(int a[],int n,int p){
    Reverse(a,0,n-1);
    Reverse(a,0,n-p-1);
    Reverse(a,n-p,n-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

9.线性表(a1,a2,a3,…,an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为x 的元素，若找到，则与其后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。

void LocateElem(Sqlist &L,int x){
    int l=0,r=L.length-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(L.data[mid]>=x){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    if(L.data[l]==x){
        if(l!=L.length-1){
            int temp;
            temp=L.data[l];
            L.data[l]=L.data[l+1];
            L.data[l+1]=temp;
        }
    }
    else{
        if(L.data[l]<x){
            L.length++;
            L.data[L.length-1]=x;
            return ;
        }
        for(int i=L.length;i>l;i--){
            L.data[i]=L.data[i-1];
        }
        L.data[l]=x;
        L.length++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

10. [2010统考真题]循环移动

1）给出算法的基本设计思想

基本设计思想：可将这个问题视作把数组ab转换成数组ba(a代表数组的前p个元素，b代表数组中余下的n-p个元素)，先将a逆置，再将b逆置，最后再整体逆置得到ba。
设Reverse函数执行将数组元素逆置的操作，Reverse中两个参数分别表示数组中待转换元素的始末位置。

2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

void Reverse(int a[],int left,int right){
    if(left>=right)return ;
    for(int i=0;i<(right-left+1)/2;i++){
        int temp=a[left+i];
        a[left+i]=a[right-i];
        a[right-i]=temp;
    }
    return ;
}
void converse(int a[],int n,int p){
    Reverse(a,0,n-1);
    Reverse(a,0,n-p-1);
    Reverse(a,n-p,n-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3）说明你设计算法的时间复杂度和空间复杂度。

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

11. [2011统考真题]找两个顺序表合并的中位数

算法思路：
分别查找两个数组的中位数
a = b，则为中位数
a < b, 中位数在 a的数组右边，b的左边
a > b, 反之
最后分别剩1个数，较小为中位数

int M_serach(int A[],int B[],int n){
    int s1=0,d1=n-1,s2=0,d2=n-1,m1,m2;
    while(s1!=d1||s2!=d2){//按照代码循环两个数组会同时终止
        m1=(s1+d1)>>1;
        m2=(s2+d2)>>1;
        if(A[m1]==B[m2]){
            return A[m1];
        }else if(A[m1]<B[m2]){
            if((s1+d1)%2){//个数为偶数
                s1=m1+1;
                d2=m2;
            }else{//个数为奇数
                d2=m2;
                s1=m1;
            }
        }else{
            if((s2+d2)%2){//个数为偶数
                s2=m2+1;
                d1=m1;
            }else{//个数为奇数
                d1=m1;
                s2=m2;
            }
        }
        //cout<<s1<<" "<<d1<<" "<<s2<<" "<<d2<<endl;
    }
    return A[m1]<B[m2] ? A[m1] : B[m2];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

类比两个有序数组排序代码：

int searchM(int A[],int B[],int n){
    int i=0,j=0,k=0;
    while(i<n&&j<n){
        if(A[i]<B[j]){
            i++;
            k++;
            if(k==n-1){
                return A[i];
            }
        }else{
            j++;
            k++;
            if(k==n-1){
                return B[j];
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

12. [2013统考真题]出现超过一半的元素

算法思路：
出现并计数，不出现–，直到0，重新计数，最终次数大于0是备选人
再进行遍历查看出现次数
空间复杂度O1，时间复杂度On

int Majority(int a[],int n){
    int c=a[0],cnt=1;
    int i=1;
    while(i<n){
        if(a[i]==c){
            cnt++;
        }else{
            if(cnt>0){
                cnt--;
            }else{
                c=a[i];
                cnt=1;
            }
        }
        i++;
    }
    if(cnt>0){
        for(int i=0;i<n;i++){
            if(c==a[i]){
                cnt++;
            }
        }
    }
    if(cnt*2>n)return c;
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

13. [2018统考真题] 数组未出现最小正整数

int searchM(int a[],int n){
    int *b;
    b=(int *)malloc(sizeof(int)*(n+1));
    memset(b,0,sizeof(b));
    for(int i=0;i<n;i++){
        if(a[i]>0&&a[i]<=n){
            b[a[i]-1]=1;
        }
    }
    int i;
    for(i=0;i<n;i++){
        if(!b[i]){
            break;
        }
    }
    return i+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

14. [2020统考真题]三元数组最小距离

思路图如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=0x3f3f3f3f3f;
const ll maxn=2e5+10;

void print(int a[],int n){
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
int abs_(int a){
    return a>0 ? a : -a;
}
int xls_min(int x,int y,int z){
    if(x<=y&&x<=z)return 1;
    if(y<=x&&y<=z)return 2;
    if(z<=x&&z<=y)return 3;
    return 0;
}
int searchM(int a[],int n,int b[],int m,int c[],int p){
    int D_min=inf;
    int i=0,j=0,k=0;
    while(i<n&&j<m&&k<p){
        int D=abs_(a[i]-b[j])+abs_(a[i]-c[k])+abs_(b[j]-c[k]);
        if(D<D_min)D_min=D;
        int val=xls_min(a[i],b[j],c[k]);
        if(val==1)i++;
        else if(val==2)j++;
        else k++;
    }
    return D_min;
}
int a[maxn]={-1,0,9},b[maxn]={-25,-10,10,11},c[maxn]={2,9,17,30,41};
int n=3,m=4,p=5;
int main()
{
    printf("%d\n",searchM(a,n,b,m,c,p));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

结语

• 遇事不决 可问春风
• 春风不语 即随本心
• 我若本心能定 怎会遇事不决 春风亦有春风愁 不劳春风为我忧。
• 自此春风盈满袖，只为一解平安愁。