跳至主要內容

2.3.3

𝓳𝓭𝔂𝓼𝔂𝓪大约 17 分钟

2.3.3

q1

  1. 从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息并退出运行。
void Del_Min(Sqlist &L, ElemType &val) {
    if (0 == L.length) {
        cout << "列表不能为空!" << endl;
        return;
    }
    // 循环一遍找到最小值
    int minIndex = 0; // 最小值的索引值
    for (int i = 0; i < L.length; ++i)
        if (L.data[i] < L.data[minIndex])
            minIndex = i;
    // 删除最小值
    val = L.data[minIndex];
    L.data[minIndex] = L.data[L.length - 1];
    L.length--;
}

int main() {
    Sqlist L;
    ElemType del_val;
    InitList(L);
    ListPush(L, 5);
    ListPush(L, 3);
    ListPush(L, 1);
    ListPush(L, 2);
    ListShow(L);
    cout << "-----" << endl;
    Del_Min(L, del_val);
    ListShow(L);
    cout << "最小值为:" << del_val << endl;
    return 0;
}

5 
3 
1 
2 
-----
5 
3 
2 
最小值为:1

q2

  1. 设计一个高效算法,将顺序表LL的所有元素逆置,要求算法的空问复杂度为 O(1)O(1)。
/**
 * 将列表元素逆置，空间复杂度为O(1)
 * 直接用双指针，交换元素位置
 * @param L
 */
void ListReverse(Sqlist &L) {
    int left = 0, right = L.length - 1;
    while (left != right && left - right != 1) {
        ElemType tmp = L.data[left];
        L.data[left] = L.data[right];
        L.data[right] = tmp;
        left++;
        right--;
    }
}

注意

需要注意while循环的条件，不是或的关系，而是与的关系

/**
 * 将列表元素逆置
 * 循环数组前半部分，与后半部分交换
 * @param L
 */
void ListReverseSingle(Sqlist &L) {
    for (int i = 0; i < L.length / 2; ++i) {
        ElemType tmp = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = tmp;
    }
}

提示

这里L.length / 2，若为偶数则整除，若为奇数，则中间位不会参与交换

q3

  1. 对长度为nn的顺序表上,编写一个时问复杂度为O(n)O(n)、空问复杂度为 O(1)O(1)的算法,该算法删除线性表中所有值为xx的数据元素。
void delElemByValue(Sqlist &L, ElemType val) {
    int k = 0;
    for (int i = 0; i < L.length; ++i)
        if (val != L.data[i]) {
            L.data[k] = L.data[i];
            k++; // 下标增加
        }
    L.length = k;
}

提示

用k记录顺序表L中不等于val的元素个数(即需要保存的元素个数),扫描时将不等于val的元素移动到下标k的位置,并更新k值。扫描结束后修改L的长度。

void delElemByValue(Sqlist &L, ElemType val) {
    int k = 0;
    for (int i = 0; i < L.length; ++i)
        if (val == L.data[i]) {
            k++;
        } else {
            L.data[i - k] = L.data[i]; // 元素前移 k 位
        }
    L.length -= k;
}

提示

用k记录顺序表L 中等于val的元素个数,边扫描L边统计k,并将不等于val的元素前移k个位置。扫描结束后修改L的长度。

q4

  1. 从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素,若s或t不合理或顺序表为空,则显示出错信息并退出运行
bool delElemByRange(Sqlist &L, ElemType s, ElemType t) {
    int k = 0;
    if (s >= t || L.length == 0)
        return false;
    for (int i = 0; i < L.length; ++i)
        if (L.data[i] <= s || L.data[i] >= t) {
            L.data[k] = L.data[i];
            k++; // 下标增加
        }
    L.length = k;
    return true;
}

提示

按照第 3 题(1)中的方案，只需要修改一下判断的条件即可，这种方案没有利用题目中有序的条件，即不管有序与否，该方法都是成立的;

提示

在很多教材中 (包括本书)指的“有序”,如无特别说明,通常是指“递增有序”

bool delElemByRange2(Sqlist &L, ElemType s, ElemType t) {
    int start, end;
    for (start = 0; start < L.length && L.data[start] < s; ++start);
    if (start >= L.length)return false;
    for (end = start; end < L.length && L.data[end] <= t; ++end);
    // 元素前移
    for (; end < L.length; start++, end++) {
        L.data[start] = L.data[end];
    }
    L.length = start;
}

相关信息

  1. 这种是书上的答案，最终效果是删除了s≤x≤ts\le x\le t之间的元素，即包括了区间的边界值
  2. 算法思想:先寻找值大于或等于s的第一个元素(第一个删除的元素),然后寻找值大于t的第一个元素(最后一个删除的元素的下一个元素),要将这段元素删除,只需直接将后面的元素前移。

按照题目要求，我觉得不应该包括边界

q5

  1. 从顺序表中删除其值在给定值s与t之问(包含s和t,要求s<t)的所有元素,若s或t不合理或顺序表为空,则显示出错信息并退出运行。

提示

类似第 3,4 题，改一下条件即可

q6

  1. 从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同
bool ListFilter(Sqlist &L) {
    if (L.length == 0)
        return false;
    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;
    return true;
}

相关信息

  1. 算法思想：注意是有序顺序表,值相同的元素一定在连续的位置上,用类似于直接插入排序的思想,初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同,若相同,则继续向后判断,若不同,则插入前面的非重复有序表的最后,直至判断到表尾为止。
  2. 需要着重注意 for循环中i和j的初始值以及循环过程中的变化
  3. 由于i代表的是索引值，是从0开始的，故数组长度为i+1
  4. 数组的第一个元素，即L.data[0]是不需要考虑的，操作数组是从L.data[1]开始的
  5. 对应的leetcode类似题目open in new window

q7

  1. 典型 将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表
bool ListMerge(Sqlist &L1, Sqlist &L2, Sqlist &L) {
    int p1 = 0, p2 = 0, k = 0;
    // 大于顾序表的最大长度
    if (L1.length + L2.length > L.MaxSize)
        return false;
    // 循环,两两比较,小者存入结果表
    while (p1 < L1.length && p2 < L2.length) {
        if (L1.data[p1] <= L2.data[p2]) {
            L.data[k++] = L1.data[p1++];
        } else {
            L.data[k++] = L2.data[p2++];
        }
    }
    // 还剩一个没有比较完的顺序表
    while (p1 < L1.length)
        L.data[k++] = L1.data[p1++];
    while (p2 < L2.length)
        L.data[k++] = L2.data[p2++];
    L.length = k;
}

相关信息

  1. 算法思想：首先,按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后,看哪个表还有剩余,将剩下的部分加到新的顺序表后面
  2. leetcode类似题目open in new window

q8

  1. 已知在一维数组A[m+n]A[m+n][1]中依次存放两个线性表(a1,a2,a3,…,am)(a_{1},a_{2},a_{3},\dots,a_{m})和(b1,b2,b3,…,bn)(b_{1},b_{2},b_{3},\dots,b_{n})。编写一个函数,将数组中两个顺序表的位置互换,即将(b1,b2,b3,…,bn)(b_{1},b_{2},b_{3},\dots,b_{n})放在(a1,a2,a3,…,am)(a_{1},a_{2},a_{3},\dots,a_{m})的前面。
/**
 * 将数组的制定区间内逆置
 * 数组是引用传值，故在函数内的操作会改变原数组的内容
 * @param A
 * @param left
 * @param right
 * @param arraySize
 */
bool reverse(DataType A[], int left, int right, int arraySize) {
    if (left >= right || right >= arraySize)
        return false;
    while (left <= right) {
        DataType tmp = A[left];
        A[left++] = A[right];
        A[right--] = tmp;
    }
    return true;
}

/**
 *
 * @param a
 * @param m 对应 A[m+n]中的m
 * @param n 对应 A[m+n]中的n
 * @param arraySize
 */
void exchange(DataType a[], int m, int n, int arraySize) {
    // 1. 整个数组逆序
    reverse(a, 0, m + n - 1, arraySize);
    // 2. a和 b 部分逆序
    reverse(a, 0, m - 1, arraySize);
    reverse(a, m, m + n - 1, arraySize);
}

int main() {
    /**
     * 假设
     * 数组 a: 1, 2, 3, 4, 5
     * 数组 b: 6, 7, 8, 9, 10
     */
    DataType a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    show(a, 10);
    exchange(a, 5, 5, 10);
    show(a, 10);
    return 0;
}

1 2 3 4 5 6 7 8 9 10 
6 7 8 9 10 1 2 3 4 5

提示

算法思想：
先将数组 A[m+n]A[m+n]中的全部元素原地逆置再对前m个元素和后 n 个元素分别使用逆置算法,从而实现顺序表的位置互换。

q9

  1. 线性表(a1,a2,a3,…,an)(a_{1},a_{2},a_{3},\dots,a_{n})中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为xx的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序.
void ListFind(DataType arr[], int arraySize, DataType val) {
    int left = 0, right = arraySize - 1, mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (arr[mid] == val) break;
        else if (arr[mid] < val) left = mid + 1;
        else right = mid - 1;
    }
    // 如果找到对应的值,交换后继元素,最后一个元素不需要交换
    if (arr[mid] == val && mid != arraySize - 1) {
        int tmp = arr[mid + 1];
        arr[mid] = arr[mid + 1];
        arr[mid + 1] = tmp;
    }
    // 没找到就插入，并保证有序
    int i;
    if (left > right) {
        for (i = arraySize - 1; i > right; --i)
            arr[i + 1] = arr[i];
        arr[i + 1] = val;
    }
}

提示

题目要求时间最少，故需要采用折半查找

警告

本题答案给出的方法并不好，本题的重点在于理解折半查找的思想，至于数据元素的插入本题方案并不好，不要管他

q10

  1. 统考真题 设将n(n>1)n(n\text{>}1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)p(0\text{<}p\text{<}n)个位置，即将R中的数据由(X0,X1,…,Xn)(X_{0},X_{1},\dots,X_{n})变换为(Xp,Xp+1,…,Xn−1,X0,X1,…,Xp−1)(X_{p},X_{p+1},\dots,X_{n-1},X_{0},X_{1},\dots,X_{p-1})要求：
    1. 给出算法的基本设计思想。
    2. 根据设计思想，采用C或 C+或 Java 语言描述算法，关键之处给出注释。
    3. 说明你所设计算法的时问复杂度和空间复杂度。
void ROL(DataType A[], int p, int arraySize) {
    reverse(A, 0, p - 1, arraySize);
    reverse(A, p, arraySize - 1, arraySize);
    reverse(A, 0, arraySize - 1, arraySize);
}

提示

  1. 算法思想：可将问题视为把数组abab 转换成数组baba(a 代表数组的前p个元素,b代表数组中余下的n一p个元素),先将a逆置得到a−1ba^{-1}b,再将bb遊置得到a−1b−1a^{-1}b^{-1},最后将整个a−1b−1a^{-1}b^{-1}逆置得到(a−1b−1)−1=ba(a^{-1}b^{-1})^{-1}=ba。设reverse [2]函数执行将数组逆置的操作
  2. 时间复杂度为O(n)O(n)空问复杂度为 O(1)O(1)

或借助辅助数组来实现。算法思想:创建大小为 p的辅助数组 S,将R中前p个整数依次暂存在S中,同时将R中后n一p 个整数左移,然后将S中暂存的p个数依次放回到 R中的后续单元。时间复杂度为 O(n)O(n)空间复杂度为 O(p)O(p)。

q11

  1. 统考真题 一个长度为L(L≥1)L(L\ge 1)的升序序列SS,处在第⌈L2⌉\displaystyle\left \lceil \frac{L}{2} \right \rceil个位置的数称为SS的中位数。例如,若序列S=(11,13,15,17,19)S=(11,13,15,17,19),则S的中位数是 15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若 S2=(2,4,6,8,20)S2=(2,4,6,8,20),则S1S_{1}和S2S_{2}的中位数是 11。现在有两个等长升序序列A和B,试设计一个在时间和空问两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:
    1. 给出算法的基本设计思想。
    2. 根据设计思想,采用C或C++或Java 语言描述算法,关键之处给出注释。
    3. 说明你所设计算法的时间复杂度和空间复杂度。
标准答案

分别求两个升序序列A,BA,B的中位数,设为aa和bb,求序列A,BA,B的中位数过程如下:

  1. 若a=ba=b,则a或ba\text{或}b即为所求中位数,算法结束。
  2. 若a<ba\text{<}b,则舍弃序列AA中较小的一半,同时舍弃序列BB中较大的一半,要求两次舍弃的长度相等。
  3. 若a>ba\text{>}b,则舍弃序列AA中较大的一半,同时舍弃序列BB 中较小的一半,要求两次舍弃的长度相等。
    在保留的两个升序序列中,重复过程1、2、3,直到两个序列中均只含一个元素时为止, 较小者即为所求的中位数。
    image.png

常规答案

int M_Search(int A[], int B[], int n) {
    // 若合并为一个数组，则长度为 2n，则中位数在 n处
    int p1 = 0, p2 = 0, k = 0;
    while (p1 < n && p2 < n) {
        bool flag = true;
        if (A[p1] < B[p2]) {
            p1++;
            flag = false;
        } else {
            p2++;
        }
        k++;
        if (k == n)
            return flag ? B[p2 - 1] : A[p1 - 1];
    }
}

int main() {
    int A[] = {1,2,3,4};
    int B[] = {4,5,6,7};
    cout << M_Search(A, B, 4) << endl;
    return 0;
}

4

提示

  1. 视频讲解open in new window
  2. 答案中的算法很优秀：通过两个序列各自求中位数，然后进行各种情况的判断，最终确定两个序列的中位数。
  3. 另一种更易想到的算法：类比归并排序的思想但并不实现归并，仅按顺序进行访问，访问⌈L2⌉\displaystyle\left \lceil \frac{L}{2} \right \rceil后即为所求(常规解法即为该方案)。
  4. 另另一种更更易想到的算法：归并排序，然后找中位元素。
  5. 最优算法的时间复杂度为O(log⁡2n)O(\log_{2}n)，空间复杂度为O(1)O(1)。次优算法(不排序仅访问)的时间复杂度是O(n)O(n)，空间复杂度为O(1)O(1)。排序后判断的算法的时间复杂度是O(n)O(n)，空间复杂度是O(n)O(n)。

警告

以上算法时间空间复杂度逐个上升，3)问只要写出自己算法对应的复杂度，正确即可得分。而前两问，如果达不到最优，只会扣1~2分。所以没有很大必要强迫自己学会最优算法，更重要的是代码的书写工整易读不出错。

int Majority(int arr[], int n) {
    int count = 0; // 计数器
    int num; // 当前计数的num
    for (int i = 1; i < n; ++i) {
        if (arr[i] == num)
            count++;
        else {
            if (count > 0) count--;
            else {
                // 更换主元素
                num = arr[i];
                count = 1;
            }
        }
    }
    // 再循环一遍得出实际出现次数
    if (count > 0)
        for (int i = count = 0; i < n; ++i)
            if (arr[i] == num) count++;
    // 判断是否为主元素
    if (count > n / 2) return num;
    else return -1;
}

q12

  1. 统考真题 已知一个整数序列A=(a0,a1,a2,…,an−1)A=(a_{0},a_{1},a_{2},\dots,a_{n-1})),其中0≤ai<n(0≤i<n)0\le a_{i}\text{<}n(0\le i \text{<}n)。若存在ap1=ap2=ap3=⋯=apm=xa_{p_{1}}=a_{p_{2}}=a_{p_{3}}=\dots=a_{pm}=x且m>n/2(0≤pk<n,1≤k≤m)m\text{>} n/2(0\le p_{k}\text{<}n,1\le k \le m),则称xx为AA的主元素。例如A=(0,5,5,3,5,7,5,5),A=(0,5,5,3,5,7,5,5),则5为主元素;又如A=(0,5,5,3,5,1,5,7)A=(0,5,5,3,5,1,5,7),则AA中没有主元素。假设AA中的nn个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出AA的主元素。若存在主元素,则输出该元素;否则输出-1。要求:
  1. 给出算法的基本设计恩想。
  2. 根据设计恩想,来用C或C++或 Java 语言描述算法,关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。
int Majority(int arr[], int n) {
    int count = 0; // 计数器
    int num; // 当前计数的num
    for (int i = 1; i < n; ++i) {
        if (arr[i] == num)
            count++;
        else {
            if (count > 0) count--;
            else {
                // 更换主元素
                num = arr[i];
                count = 1;
            }
        }
    }
    // 再循环一遍得出实际出现次数
    if (count > 0)
        for (int i = count = 0; i < n; ++i)
            if (arr[i] == num) count++;
    // 判断是否为主元素
    if (count > n / 2) return num;
    else return -1;
}

q13

  1. 统考真题 给定一个含n(n≥1)n(n\ge1)个整数的数组,请设计一个在时问上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。要求:
    1)给出算法的基本设计思想。
    2)根据设计思想,采用C或Ct+语言描述算法,关键之处给出注释。
    3)说明你所设计算法的时间复杂度和空间复杂度。
int findMissMin(int arr[], int n) {
    int *p = (int *) malloc(sizeof(int) * n);
    int res, j;
    // 遍历一遍arr,如果存在1 ~ n 之间的数，则在对应数组位置标为 1
    for (int i = 0; i < n; ++i) {
        if (arr[i] >= 1 || arr[i] <= n)
            p[arr[i] - 1] = 1;
    }
    // 遍历一遍记录数组
    for (j = 0; j < n; ++j) {
        if (p[j] == 0) {
            res = j + 1;
            break;
        }
    }
    // 如果全为 1
    if (j == n) res = n;
    return res;
}

提示

  • 算法思想：题目要求时间尽量高效，故采取空间换时间的算法，新建一个辅助数组用来标记数组中的数有没有出现，若出现则标记为 1，否则则默认为 0；然后遍历该记录数组，若有下标元素为 0，则res = j+1,否则res=n
  • 时间复杂度为O(n)O(n),空间复杂度为O(n)O(n)
  • 原书笔记链接

q14

  1. 统考真题 定义三元组a,b,ca,b,c(a,b,ca,b,c均为整数)的距离D=∣a−b∣+∣b−c∣+∣c−a∣D=|a-b|+|b-c|+|c-a|。给定了个非空整数集合S1,S2,S3S_{1},S_{2},S_{3},按升序分別存储在3个数组中。请设计一个尽可能高效的算法,计算并输出所有可能的三元组(a,b,c)(a∈S1,b∈S2,c∈S3)(a,b,c)(a\in S_{1},b\in S_{2},c\in S_{3})中的最小距离。例如S1={−1,0,9},S2={−25,−10,10,11,},S3={2,9,17,30,41}S_{1}=\{-1,0,9\},S_2=\{-25,-10,10,11,\},S_{3}=\{2,9,17,30,41\},则最小距离为2,相应的三元组为(9,10,9)(9,10,9)。要求:
    1)给出算法的基本设计思想。
    2)根据设计思想,采用C语言或C†+语言描述算法,关键之处给出注释。
    3)说明你所设计算法的时问复杂度和空问复杂度。
int abs(int a) {
    return a > 0 ? a : -a;
}

/**
 * 判断 a 是否为最小值
 * @param a
 * @param b
 * @param c
 * @return
 */
bool isMin(int a, int b, int c) {
    if (a <= b && a <= c) return true;
    return false;
}

int findMinDis(int A[], int a, int B[], int b, int C[], int c) {
    int i = 0, j = 0, k = 0, d;
    int d_min = abs(A[0] - B[0]) + abs(B[0] - C[0] + abs(A[0] - C[0])); // 初始距离
    // 每一轮循环最小值对应的变量+1
    while (i < a && j < b && k < c) {
        d = abs(A[i] - B[j]) + abs(B[j] - C[k] + abs(A[i] - C[k])); // 当前距离
        if (d < d_min) d_min = d; // 更新最小值
        if (isMin(A[i], B[j], C[k])) i++;
        else if (isMin(B[j], C[k], A[i])) j++;
        else k++;
    }
    return d_min;
}

注意

  1. 在下面的分析过程中，我们默认a≤b≤ca\le b \le c，这和代码中的a,b,ca,b,c代表含义不同
  2. 题目中说明，集合中元素为升序

提示

  • 算法思想
  • 视频讲解open in new window
  • 可知，DD的大小取决于a,ca,c之间的距离，故我们在循环过程中，每次找到最小值元素所在集合，下一轮循环就为该集合的下一个元素，这是因为只有移动较小元素，才可能让距离变小

  1. 这里m+nm+n的理解方式，书上好像有点误解，书上最终给出的exchange函数中m和n有点混淆 ↩︎

  2. 参考第 8 题中reverse函数的实现 ↩︎

默认页脚
Copyright © 2023 𝓳𝓭𝔂𝓼𝔂𝓪