从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
算法的代码描述如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18Elemtype deleteMin(Sqlist &arr) { //可以考虑形参中引入 &min，
if (arr.length == 0 && arr == null) {
printf("The array is empty.");
return 0;
} else {
Elemtype min = arr[0];
int index = 0;
for(int i = 1; i <= arr.length; i++) {
if (arr[i] <= min) {
min = arr[i];
index = i;
}
}
arr[index] = arr[arr.length - 1];
arr.length--;
return min;
}
}
设计一个高效算法，将顺序表L的所有元素逆置,要求算法的空间复杂度为\(O(1)\)。
算法的代码描述如下：
1
2
3
4
5
6
7void reverse(Sqlist &arr) {
for (int i = 0; i <= arr.length / 2; i++) {
Elemtype temp = arr[i];
arr[i] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = temp;
}
}
对长度为n的顺序表L，编写一个时间复杂度为\(O(n)\)、空间复杂度为\(O(1)\)的算法,该算法删除线性表中所有值为x的数据元素。
算法的代码描述如下：
1
2
3
4
5
6
7
8
9void deleteX(int x, Sqlist &L) {
for (int i = 0; i <= L.length; i++){
if(L[i] == x) {
L[i] = L[L.length - 1];
L.length--;
i--;
}
}
}
上述方法造成顺序表较之前乱序，下面方法更好。
1
2
3
4
5
6
7
8
9
10void deleteX(Elemtype x, Sqlist &L) {
int count = 0; //记录不等于x的元素的个数
for(int i = 0; i <= L.length; i++) {
if(L[i] != x) {
L[k] = L[i];
k++
}
L.length = k;
}
}
从有序顺序表中删除其值在给定值s与t之间（要求 \(s<t\)）的所有元素,如果s或t不合理或顺序表为空,则显示出错信息并退出运行。
算法的代码描述如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19bool deleteS2T(Elemtype s, Elemtype t, Sqlist &L) {
if (s > L[L.length - 1] || t < L[0] || s < t ||L.length == 0) {
cout << "Error!" << endl;
return false;
}
int count, index = 0; //记录st之间的元素的个数,以及区间最后一个元素的index
for(int i = 0; i <= L.length; i++) {
if(L[i] >= s && L[i] <= t) {
count++;
index = i;
}
}
for(int i = index - count; index < L.length; i++) {
L[i] = L[index];
index++;
}
L.length -= count;
return true;
}
从顺序表中删除其值在给定值s与t之间（包含s和t,要求\(s<t\)）的所有元素,如果s或t不合理或顺序表为空,则显示出错信息并退出运行。
算法的代码描述如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16bool deleteS2T(Elemtype s, Elemtype t, Sqlist &L) {
int count;
if (s > t || L.length = 0) {
cout << "Error!" << endl;
return false;
}
for (int i = 0; i < L.length; i++) {
if (L[i] >= s && L[i] <= t) {
count++;
} else {
L[i - count] = L[i];
}
}
L.length -= count;
return true;
}
从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同。
算法的代码描述如下：
1
2
3
4
5
6
7
8
9void deleteRepeat(Sqlist &L) {
for (int i, i < L.length, i++) {
if(L[i] == L[i + 1] && i - 1 <= L.length) {
L[i + 1] = L[i + 2]
i--;
L.length--;
}
}
}
上述方法一次删除一个，对连续重复元素处理的效率低。
1
2
3
4
5
6
7
8
9void deleteRepeat(Sqlist &L) {
int i, j;
for (i = 0, j = 1; j < L.length, j++) {
if(L[i] != L[j]) {
L[++i] = L[j];
}
}
L.length = i + 1;
}
将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表。
算法的代码描述如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19Sqlist merge(Sqlist A, Sqlist B) {
Sqlist C;
int i, j, k = 0;
while(i < A.length && j < B.length) {
if(A[i] <= B[j]) {
C[k++] = A[i++];
} else {
C[k++] = B[j++];
}
while (i < A.length) {
C[k++] = A[i++];
}
while (j < B.length) {
C[k++] = B[j++];
}
}
C.length = k;
return C;
}
已知在一维数组\(A[m+n]\)中依次存放两个线性表\((a_1,a_2,a_3,...,a_m)\)和\((b_1,b_2,b_3,...,b_n)\)。试编写一个函数,将数组中两个顺序表的位置互换，即将\((b_1,b_2,b_3,...,b_n)\)放在\((a_1,a_2,a_3,...,a_m)\)的前面。
算法的代码描述如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14// 给定顺序表L，倒置其索引在start，end之间的全部元素
void reverse(Sqlist &L, int start, int end) {
for(int i = start; i < (start + end) / 2; i++) {
Elemtype temp = L[i];
L[i] = L[end - i];
L[end - i] = temp;
}
}
void exchange(Sqlist &L, int m, int n) { //m, n分别对应两子表长度。
reverse(L, 0, m + n - 1);
reverse(L, 0, n - 1);
reverse(L, n, m + n - 1);
}
线性表\((a_1,a_2,a_3,...,a_n)\)中的元素递增有序且按顺序存储于计算机内。要求设计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使表中元素仍递增有序。
算法的代码描述如下：
1 | void searchExchangeOrInsert(Sqlist &L, Elemtype x){ |
设将\(n(n>1)\)个整数存放到一维数组R中。 设计一个在时间和空间两方面都尽可能高效的算法。 将R中保存的序列循环左移\(p(0<p<n)\)个位置,即将R中的数据由\((X_0,X_1,...,X_{n-1})\)变换为\((X_p,X_{p+1},...,X_{n-1},X_0,X_1,...,X_{p-1})\)。要求:
给出算法的基本设计思想。
根据设计思想,采用C或C++或 Java语言描述算法,关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。
解答：
最直观的办法是构建一个辅助数组，将R中的元素，放置在辅助数组的对应位置上，只需遍历一次，时间复杂度\(O (n)\)，空间复杂度也是\(O(n)\)。
可以考虑将数组划分为两部分ab，a的长度为p，目标数组实际上是ba。具体方法，首先倒置a，然后倒置b，接着倒置整个数组。数学形势可表达为 \(ba = (a^{-1}b^{-1})^{-1}\)。
1
2
3
4
5
6
7
8
9
10
11
12
13void reverse(int R[], int start, int end) {
for(int i = start; i < (start + end) / 2; i++) {
int temp = R[i];
R[i] = R[end - i];
R[end - i] = temp;
}
}
void cycleLeft(int R[], int p, int n) {
reverse(R, 0, p - 1);
reverse(R, p, n - 1);
reverse(R, 0, n - 1);
}时间复杂度为\(O(p/2) + O((n-p)/2) + O(n) = O(n)\)，空间复杂度为\(O(1)\)。
一个长度为\(L(L\geq 1)\)的升序序列S，处在第\([L/2]\)个位置的数称为S的中位数。例如,若序列\(S_1=(11,13,15,17,19)\)，则\(S_1\)的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若\(S_2=(2,4,6,8,20)\)，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:
给出算法的基本设计思想。
根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。
解答：
考虑到两序列等长升序，可以考虑对两数组长度和的前一半进行排序。分别设置两指针分别指向两数组的头位置，每次比较两指针指向元素的大小，小的指针自增。易知时间复杂度为\(O(n)\)。
另解：分别求A，B两序列的中位数，设为a, b
a. 若a = b，则中位数为a或b，算法结束
b. 若a < b，则舍去A较小的部分，舍去B较大的部分，反之亦然。
重复上述步骤，直至两序列都只剩下一个元素。较小者为所求中位数。
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
29int search4Median(int A[], int B[], int n) {
int s1 = 0, e1 = n - 1, s2 = 0, e2 = n - 1;//s表示序列开头，e表示序列结尾
int m1, m2
while(s1 != e1 && s2 != e2) {
m1 = (s1 + e1) / 2;
m2 = (s2 + e2) / 2;
if (A[m1] == B[m2]) {
return m1;
}
if (A[m1] < B[m2]) {
if ((e1 - s1) % 2 == 0) { //序列元素为奇数
s1 = m1;
e2 = m2;
} else { //序列元素为偶数
s1 = m1 + 1;
e2 = m2;
}
} else {
if ((e1 - s1) % 2 == 0) { //序列元素为奇数
s2 = m2;
e1 = m1;
} else { //序列元素为偶数
s2 = m2 + 1;
e1 = m1;
}
}
}
return (A[s1] < B[s2]) ? A[s1] : B[s2];
}时间复杂度为\(O(log_2n)\)，空间复杂度为\(O(1)\)。
已知一个整数序列\(A=(a_0,a_1,...,a_{n-1})\)，其中\(0\leq a_n < n (0\leq i<n)\)。若存在\(a_{p1}=a_{p2}=...=a_{pm}=x\)且\(m>\frac{n}{2} (0\leq 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。要求：
给出算法的基本设计思想。
根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。
解答：
序列中某一元素个数大于序列元素总个数的一半时，该元素为主元素。设置一个辅助数组，长度为n，其key值对应原序列元素的value值，其value值记录该序列元素出现的次数。
a. 第一遍遍历原序列，生成辅助数组。
b. 遍历辅助数组，查找是否有值大于原序列长度的一半，如有输出对应key值，如没有输出\(-1\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int searchMain(int A[], int n) {
int B[n];
for (int i = 0; i < n; i++) {
B[i] = 0; //初始化辅助数组
}
for (int i = 0; i < n; i++) {
B[A[i]]++;
}
for (int i = 0; i < n; i++) {
if (B[i] > n / 2) {
return i
}
}
return -1;
}- 时间复杂度为\(O(n)\)，空间复杂度为\(O(n)\)。
给定一个含\(n(n\geq 1)\)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组\([-5,3,2,3]\)中未出现的最小正整数是1; 数组\([1,2,3]\)中未出现的最小正整数是4。要求:
给出算法的基本设计思想。
根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。
解答：
考虑题12解法，通过空间换取时间。假设A是连续升序序列，则索引\(0 \sim (n-1)\)对应\(1 \sim n\)，此时缺失最小整正整数为\(n +1\)，如果不连续，可以知道目标值一定在\(1 \sim n\)之中。所以设置辅助数组长度为\(n+1\)。
a. 遍历原序列，为辅助数组赋值。
b. 遍历辅助数组，寻找第一个值为零的索引值，并输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14int searchMain(int A[], int n) {
int B[n + 1];
for (int i = 0; i < n + 1; i++) {
B[i] = 0; //初始化辅助数组
}
for (int i = 0; i < n; i++) {
B[A[i]]++;
}
for (int i = 0; i < n + 1; i++) {
if (B[i] == 0) {
return i
}
}
}时间复杂度为\(O(n)\)，空间复杂度为\(O(n)\)。