Question

已知一顺序表 A ，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素

Answer 1

问：已知一顺序表 A ，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素

答：顺序表 A 中的元素值非递减有序排列，因此相同的元素必定是相邻的。为了删除重复的元素，可以遍历整个顺序表 A，同时记录两个指针 i 和 j，其中 i 指向当前已经处理好的无重复元素的位置，j 则从 i+1 开始向后扫描。每次比较 A[i] 和 A[j] 的值，如果它们相等，则 j 继续向后移动；否则，将 A[j] 的值赋给 A[i+1]，同时将 i 和 j 均向后移动一个位置。这样遍历完之后，前 i 个元素即为不重复的元素。下面是表示上述算法的伪代码：```i = 0for j from 1 to n-1: if A[j] != A[i]: i = i + 1 A[i] = A[j]return i + 1```其中 n 是顺序表 A 的长度，返回值 i+1 即为删除重复元素之后的顺序表长度。这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。

问：写一个算法，从一个给定的顺序表 A 中删除值在 x ~ y ( x <= y ）之间的所有元素，要求以较高的效率来实现

答：假设顺序表 A 存储在一个数组中，数组长度为 n。为了高效地删除值在 x ~ y 之间的元素，可以采用类似于快速排序的方法，将满足条件的元素移到数组的左侧，不满足条件的元素移到数组的右侧。具体来说，可以维护两个指针 i 和 j，分别从数组的两端开始向中间扫描。当 A[i] 的值在 x 和 y 之间时，将其与 A[j] 交换，并使 j 向左移动一位；否则，i 向右移动一位。这样遍历完之后，数组前 j 个元素就是不满足条件的元素，而数组后 i-j 个元素就是满足条件的元素，将其删除即可。下面是表示上述算法的伪代码：```i = 0j = n - 1while i <= j: if x <= A[i] <= y: while x <= A[j] i: j = j - 1 A[i] = A[j] j = j - 1 else: i = i + 1return i```

答：其中 x 和 y 是删除的范围，n 是数组长度，返回值 i 即为删除之后数组的长度。这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。由于只需要对数组进行一次遍历，因此效率较高。

问：线性表中有 n 个元素，每个元素是一个字符，现存于向量 R [ n ］中，试写一算法，使 R 中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。

答：可以使用三路快排的思路来解决这个问题。算法步骤如下：1. 设置三个指针 i、j、k，其中 i 表示字母字符区间的右界，j 表示数字字符区间的右界，k 表示其它字符的右界。2. 依次扫描 R [1...n] 中的每个元素，遇到字母字符则将该元素与 R[i+1] 交换，并更新 i；遇到数字字符则将该元素与 R[j+1] 交换，并更新 j；否则将该元素与 R[k+1] 交换，并更新 k。3. 扫描结束后，R [1...i] 区间内为字母字符，R [(i+1)...j] 区间内为数字字符，R [(j+1)...k] 区间内为其它字符。分别对这三个区间递归地使用上述算法进行排序。4. 完成排序后，R [1...n] 按照字母字符、数字字符和其他字符的顺序排列。这个算法使用原地排序，即只需要利用原来的存储空间，移动元素的次数最小。时间复杂度：O(nlogn)。参考代码如下（C++实现）：

答：cpp复制代码void sort(char R[], int left, int right) { if (left >= right) return; int i = left - 1, j = left - 1, k = left - 1; char pivot = 'a' - 1; // 设置一个哨兵 for (int p = left; p = 'a' && R[p] <= 'z') { ++i; swap(R[i], R[p]); if (R[i] pivot) { // 更新哨兵 pivot = R[i]; } } else if (R[p] >= '0' && R[p] <= '9') { ++j; swap(R[j], R[p]);

答：sort(R, left, i); sort(R, i+1, j); sort(R, j+1, k);}

问：线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前 m 个元素和后 n 个元素进行整体互换。即将线性表：( al , az ,..., am , bi ,b2,..., bn ）改变为：( bj , bz ,..., bn , ai , az ,..., am )。

答：题目描述：用顺序存储方式存储线性表，设计一个算法将顺序表中前 m 个元素和后 n 个元素进行整体互换。即将线性表：( al , az ,..., am , bi ,b2,..., bn ）改变为：( bj , bz ,..., bn , ai , az ,..., am )。解题思路：该问题可以通过三次逆置实现，首先将前m个元素逆置，然后将后n个元素逆置，最后将整个线性表逆置，就可以达到题目所述的要求。具体实现：1. 首先设立两个指针left和right，分别指向线性表的第一个元素和第m个元素；2. 对left到right之间的元素进行逆置；3. 同理，设立两个指针left和right，分别指向线性表的第n+1个元素和最后一个元素；4. 对left到right之间的元素进行逆置；5. 最后对整个线性表进行逆置即可得到所要求的结果。

答：代码实现：复制代码#include #define MAXSIZE 100typedef struct { int data[MAXSIZE]; int length;} SqList;void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp;}void reverse(SqList *L, int left, int right) { // 将顺序表L中left到right之间的元素逆置 while (left right) { swap(&L->data[left], &L->data[right]); left++; right--; }}

答：void exchange(SqList *L, int m, int n) { // 将顺序表L中前m个元素和后n个元素进行整体互换 reverse(L, 1, m); reverse(L, m+1, m+n); reverse(L, 1, m+n);}int main() { SqList L = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 10}; printf("The original sequence list is: "); for (int i = 1; i <= L.length; i++) { printf("%d ", L.data[i]); } // 将前3个元素和后4个元素进行整体互换 exchange(&L, 3, 4); printf("\nAfter exchanged, the sequence list is: "); for (int i = 1; i <= L.length; i++) {

答：运行结果：复制代码The original sequence list is: 0 1 2 3 4 5 6 7 8 9 After exchanged, the sequence list is: 4 5 6 7 8 9 0 1 2 3 时间复杂度：O(n)空间复杂度：O(1)