logo
HextalHyperion
banner
NEWS LETTER

顺序表综合题解析

Scroll down

我指针(索引)玩得贼溜~

重温一下王道复习书上几道关于顺序表的综合题的题目及解题思路。


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

【思路】：如果真傻傻地去认真寻找每一个x，然后使用前面学过的最正统的删除操作进行的话，那么时间复杂度很可能达到O(n2）,这一题考的不是按部就班的寻找删除，而是巧妙地利用顺序存储的规则和对题目的理解，实现覆盖操作。

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
// 法一：思考当所有x被删除后，表中剩余元素会前移，而每个元素前移的量就是其前面x的个数
// 遍历顺序表，记录遇到值为x的元素的个数（设为cnt），遇到值不是x的元素，则前移cnt位
void delMin(SqList &L) {
    int cnt = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == x) {
            cnt++;
        } else {
            L.data[i - cnt] = L.data[i];
        }
    }
    // 记得修改L的长度
    L.length -= cnt;
}

// 法二：逆向思考，遇到非x的元素，则往前移动，类似插入排序
// 遍历顺序表，维护一个变量cnt，每遇到一个非x的元素，则往前移动到cnt位置，并cnt加1
void delMin(SqList &L) {
    int cnt = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] != x) {
            L.data[cnt] = L.data[i];
            cnt++;
        }
    }
    // 修改L的长度
    L.length = cnt;
}

这一题充分利用了顺序表的存储结构，不是真的进行标准的删除操作，而是用覆盖元素的和修改length的方式达到相同的效果。实际上标准的删除操作说到底也是覆盖元素加修改length的操作，当顺序表中只有一个x时，整个流程就是标准的删除操作的流程。这启示我们，不能生搬硬套，一定要用计算机的思维去分析问题，处理问题。


【题目2】：从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

【思路】：这又是一道关于删除元素的题目，那么有了上一题的经验，这一题我们同样要发出质问：真的要进行标准删除操作吗？当然不是，我们需要执行的仍然是元素覆盖加改变length的操作。而且这一题还是有序顺序表，这无疑又给我们提供了很大的便利——重复的元素都挨在一起，我们只需要按顺序遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
// 本题同样有两种方法：记录重复元素个数，遇到不重复的元素前移；或者记录不重复的元素个数，用一个新的索引表示新的顺序表的长度
// 0 1 1 2 2 2 3 4 4 5   --> 0 1 2 3 4 5 
void delSame(SqList &L) {
    int idx = 0;// 表示新的顺序表的当前末尾索引
    for (int i = 1; i < L.length; i++) { // i从1开始，与i-1进行比较
        if (L.data[i] != L.data[i - 1]) { // 此处亦可写成 L.data[i] != L.data[idx]
            L.data[++idx] = L.data[i]; 
        }
    }
    // idx表示新的顺序表的索引，所以长度需要加1
    L.length = idx + 1;
}


【题目3】：已知一维数组A[m+n]中依次存放两个线性表(a1,a2,...,am)和(b1,b2,...,bn)。编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,...,bn)放在(a1,a2,...,am)的前面。

【思路】：此题乍一看无从下手，如何规划过程才能使得两个部分达到交换的效果呢？当然没有一蹴而就的方法，我们需要通过几次间接的逆置操作完成。在离散数学中有一个知识点，对于序列AB，要想达到BA，可以先整体逆置，在分别对每个部分逆置，即由AB -> (AB)-1 ,此时即为B-1A-1,之后再进行分别逆置，即(B-1)-1(A-1)-1,最终可以得到BA。类似的原理也常用与矩阵的运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void reverse(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
void exchange(int arrr[], int m, int n) {
    // 整体逆置
    reverse(arr, 0, m + n - 1);
    //分别逆置
    reverse(arr, 0, n - 1);
    reverse(arr, n, n + m - 1);
}

这一题需要牢记逆置的思路，如果以后出现了ABC三个序列逆置的问题，也是同样的处理方法，先整体逆置，再对每个部分分别逆置。


【题目4 - 2018统考】：给定一个含n（n>=1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。

【思路】：最简单的方法是从1开始挨个寻找数组中是否存在当前正整数，妥妥的双重for循环，O(n2)的时间复杂度，在紧张想不出思路的情况下完全可以用，但就是不太优雅。那么有没有更好一点的思路呢？当然有的！题目中只强调时间上尽可能高效，但没有提及对空间的要求，所以我们大可以利用额外的存储空间来做一些文章，辅助解决问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 新建一个辅助数组，长度也为n，若原数组中遇到某个正整数，则将辅助数组中对应下标的位置修改为1，完成之后遍历辅助数组，遇到值为0的元素则返回
void findMissMin(int A[], int n) {
    int *B = (int *)malloc(n * sizeof(int)); // 给B分配内存空间
    memset(B, 0, n * sizeof(int)); // 将B中元素全部置为0
    for (int i = 0; i < n; i++) {
        if (A[i] > 0 && A[i] <= n) {
            B[A[i] - 1] = 1;
        }
    }
    // 遍历B，遇到0则跳出
    for(int i = 0; i < n; i++) {
        if (B[i] == 0) {
            break;
        }
    }
    return i + 1;
}

有几个注意点：

  1. 为什么辅助数组B的长度也要设置为n?

因为A的长度是n，但凡A中出现了非正数或者大于n的数，那么A在1-n中必然有缺失，极端情况即为A中恰好是1-n,B也能够存储下。

  1. 为什么最后返回i + 1?

因为设置的时候就是B[A[i] - 1],为了照顾索引和容纳最大的元素个数而设计的思路。

  1. 极端情况(A中元素就是1-n)下可以跑通吗?

在极端情况下，不会执行break语句，会自然退出，此时i=n，返回i+1即为n+1,符合题目要求，依然可以跑通

其他文章
高数
高数第9讲基本积分公式巩固
  • 24/03/25
  • 19:49
10 +
Completed Projects
140 +
Honors and Awards