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

  1. 时间复杂度为 o（n^2）的暴力算法，即两个for循环。

  2. 记录不等于x的元素的个数
    相比较与粘图片，还是使用福昕pdf复制，我觉得还是手打吧，因为我实在是看不上前两种方式

法一：记录不等于x的个数，直接替换

1
2
3
4
5
6
7
8
9
10
void del(SeList *L,Element x){
    int k = 0;//记录不等于x的个数
    for(int i = 0 ; i < L->length;i++){
        if (L->data[i] != x){
            L->data[k] = L->data[i];
            k++;
        }
    }
    L->length = k ;
}

法二：记录等于x的个数，整体移位

1
2
3
4
5
6
7
8
9
10
11
void del(SeList *L,Element x){
    int k = 0,i = 0 ;
    while(i < L->length){
        if(L->data[i] == x){
            k++;
        }else{
            data[i-k] = data[i];
        }
    }
    L->length = L->length-k;
}

法三：双指针法

变种

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

合并有序表为一个新的有序表，并由函数返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool Merge(SqList *a,SqList *b ,SqList *c){
    if(a->length + b->length > c->length){
        return false;
    }
    int i = 0 , j = 0 , k = 0 ;
    while(i < a->length && j < b->length){
        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;
}

如图

404

思路：先对m+n整体逆转，在对其分别逆转。

1
2
3
4
5
6
7
8
9
10
11
12
bool Reverse(SqList *L,int left,int right,int arraySize){
    if(right - left > arraySize){
        return false;
    }
    int mid = (right - left)/2 + left;
    for(int i = 0 ; i <= mid ; i++){
        int temp = L->data[left + i];
        L->data[left + i] = L->data[right - i];
         L->data[right - i] = temp;
    }
    return true;
}
1
2
3
4
5
bool Exchange(SqList *L,int left,int right,int arraySize){
    Reverse(&L,0,m+n-1,m+n);
    Reverse(&L,0,n-1,n);
    Reverse(&L,n,m+n-1,m);
}

变种

404

从三个顺序表中找出相同元素

404

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sameKey(int a[],int b[],int c[],int n){
    int i = 0 , j = 0 ,k = 0; 
    while(i < n && j < n && k < n){
        if(a[i] == b[j] && b[j] == c[k]){
            printf("%d\n",a[i]);
            i++;
            j++;
            k++;
        }else{
            int max = maxValue(a[i],maxValue(b[j],c[k]));
            if(a[i] < max){i++;}
            if(a[j] < max){j++;}
            if(a[k] < max){k++;}
        }
    }
}

时间复杂度，o(n)
空间复杂度，o(1)