• 数据结构02附录01：顺序表考研习题[C++]

     

      图源：文心一言

    考研笔记整理~🥝🥝

    之前的博文链接在此：数据结构02：线性表[顺序表+链表]_线性链表-CSDN博客~🥝🥝

    本篇作为线性表的代码补充，每道题提供了优解和暴力解算法，供小伙伴们参考~🥝🥝

    • 第1版：无情地Push Chat GPT老师写代码、分析GPT老师写的代码并思考弱智解~🧩🧩

    编辑：梅头脑🌸

    参考用书：王道考研《2024年 数据结构考研复习指导》

    📇目录

    📇目录

    🧵2010统考真题

    🧩题目

    🌰优解 

    📇优解思路

     ⌨️优解代码

     ⌨️优解演算 

    🌰暴力解

    📇暴力解思路

    ⌨️暴力解代码

    ⌨️暴力解演算

    🧵2011统考真题

    🧩题目

    🌰优解 

    📇优解思路

     ⌨️优解代码

     ⌨️优解演算 

    🌰暴力解

    📇暴力解思路

    ⌨️暴力解代码

    ⌨️暴力解演算

    🧵2013统考真题

    🧩题目

    🌰优解 

    📇优解思路

     ⌨️优解代码

     ⌨️优解演算 

    🌰暴力解

    📇暴力解思路

    ⌨️暴力解代码

    ⌨️暴力解演算

    🧵2018统考真题

    🧩题目

    🌰优解 

    📇优解思路

     ⌨️优解代码

    🧵2020统考真题

    🧩题目

    🌰优解 

    📇优解思路

     ⌨️优解代码

    🌰暴力解

    📇暴力解思路

    ⌨️暴力解代码

    🔚结语

    🧵2010统考真题

    🧩题目

    设将n个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p个位置，即将R的数据由(X0，X1，…，Xn-1)变换为(Xp，Xp+1，…Xn-1，X0，X1，…，Xp-1)。

    🌰优解 

    📇优解思路

    • 算法思想：
      • 将数组p(n-p)转化为数组(n-p)p，(n-p)p=(p-1(n-p)-1)-1；
      • 因此分别反转前p项，后n-p项，最后整体反转p-1(n-p)-1；
      • reverse函数用于反转数组中指定范围的元素，它通过交换两端的元素来实现反转。
    • 时间复杂度：O(n)，其中n是数组的长度，因为需要反转数组的两部分和整体数组。
    • 空间复杂度：O(1)，因为算法只使用了固定的额外空间来存储一些临时变量，与数组的长度无关。

     ⌨️优解代码

    1. #include 
    2. using namespace std;
    3.  
    4. // 反转数组中指定范围的元素
    5. void reverse(int arr[], int start, int end) {
    6.     // 使用双指针法将数组中指定范围的元素进行反转
    7.     // start 指向要反转的范围的起始位置，end 指向要反转的范围的末尾位置
    8.  
    9.     while (start < end) {
    10.         // 交换 start 和 end 位置的元素
    11.         int temp = arr[start];
    12.         arr[start] = arr[end];
    13.         arr[end] = temp;
    14.  
    15.         // 向中间移动双指针
    16.         start++;
    17.         end--;
    18.     }
    19. }
    20.  
    21. // 执行循环左移操作
    22. void rotateLeft(int arr[], int n, int p) {
    23.     // 将左移位数取模以确保它在数组长度范围内
    24.     p = p % n;
    25.     if (p == 0) return; // 如果左移位数为0，直接返回，不需要进行操作
    26.     reverse(arr, 0, p - 1); // 反转前半部分
    27.     reverse(arr, p, n - 1); // 反转后半部分
    28.     reverse(arr, 0, n - 1); // 整体反转
    29. }
    30.  
    31. int main() {
    32.     const int n = 10; // 数组长度为10
    33.     const int p = 3; // 左移3位
    34.  
    35.     int arr[n] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 初始化数组元素
    36.  
    37.     rotateLeft(arr, n, p); // 执行左移操作
    38.  
    39.     // 输出结果
    40.     cout << "左移后的数组为: ";
    41.     for (int i = 0; i < n; i++) {
    42.         cout << arr[i] << " ";
    43.     }
    44.  
    45.     return 0;
    46. }

     ⌨️优解演算 

    • 初始轮 arr[n] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; temp = NULL；
    • 第一轮 arr[n] = {2, 1, 0, 3, 4, 5, 6, 7, 8, 9}; temp = 0；
    • 第二轮 arr[n] = {2, 1, 0, 9, 8, 7, 6, 5, 4, 3}; temp = 3；temp = 4；temp = 5；
    • 第三轮 arr[n] = {3, 4, 5, 6, 7, 8, 9, 0, 1, 2}; temp = 2；temp = 1；temp = 0；temp = 9；temp = 8；

    🌰暴力解

    📇暴力解思路

    • 算法思想：
      • 创建一个临时数组 temp，用于存储前p个元素。
      • 将后面的元素向前移动p个位置，留出前p个位置用于粘贴临时数组的内容。
      • 将临时数组中的元素复制回原数组的末尾。
    • 时间复杂度：O(n)，因为我们额外使用了一个临时数组 temp 来存储前p个元素。这个临时数组的大小与左移的位数p相等，因此空间复杂度是O(p)，而在最坏情况下，p可以等于n，所以空间复杂度可以达到O(n)。
    • 空间复杂度：O(n)，理由同上。

    ⌨️暴力解代码

    1. #include 
    2. using namespace std;
    3.  
    4. void rotateLeft(int arr[], int n, int p) {
    5.     int temp[p]; // 创建一个临时数组用于存储前p个元素
    6.  
    7.     // 复制前p个元素到临时数组中
    8.     for (int i = 0; i < p; i++) {
    9.         temp[i] = arr[i];
    10.     }
    11.  
    12.     // 将后面的元素向前移动p个位置
    13.     for (int i = p; i < n; i++) {
    14.         arr[i - p] = arr[i];
    15.     }
    16.  
    17.     // 将临时数组中的元素复制回原数组末尾
    18.     for (int i = 0; i < p; i++) {
    19.         arr[n - p + i] = temp[i];
    20.     }
    21. }
    22.  
    23. int main() {
    24.     const int n = 10; // 数组长度为10
    25.     const int p = 3; // 左移3位
    26.  
    27.     int arr[n] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 初始化数组元素
    28.  
    29.     rotateLeft(arr, n, p); // 执行左移操作
    30.  
    31.     // 输出结果
    32.     cout << "左移后的数组为: ";
    33.     for (int i = 0; i < n; i++) {
    34.         cout << arr[i] << " ";
    35.     }
    36.  
    37.     return 0;
    38. }

    ⌨️暴力解演算

    • 初始轮 arr[n] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; temp[p] = NULL；
    • 第一轮 arr[n] = {2, 1, 0, 3, 4, 5, 6, 7, 8, 9}; temp[p] = {2, 1, 0}；
    • 第二轮 arr[n] = {3, 4, 5, 6, 7, 8, 9, 7, 8, 9}; temp[p] = {2, 1, 0}；
    • 第三轮 arr[n] = {3, 4, 5, 6, 7, 8, 9, 0, 1, 2}; temp[p] = {2, 1, 0}；

    🧵2011统考真题

    🧩题目

    一个长度为L的升序序列S，处在第[L/2]个位置的元素称为S的中位数。例如，若序列S1=（11,13,15,17,19），则S1的中位数是15，两个序列的中位数是他们所有元素的升序序列的中位数。例如若S2=（2,4,6,8,10），则S1和S2的中位数是11。现在有两个等长的升序序列A和B，试设计在一个时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

    🌰优解 

    📇优解思路

    • 算法思想：
      • 检查A和B的中间位置的元素，分别记为a_mid和b_mid。

        • 如果a_mid等于b_mid，那么它们就是两个序列的中位数，直接返回a_mid或b_mid都可以。

        • 如果a_mid小于b_mid，说明A的中位数位于A的后半部分和B的前半部分之间，将A的前半部分和B的后半部分丢弃，继续在剩下的部分中查找中位数。

        • 如果a_mid大于b_mid，说明B的中位数位于B的后半部分和A的前半部分之间，将B的前半部分和A的后半部分丢弃，继续在剩下的部分中查找中位数。

      • 重复上述步骤，直到找到中位数。
    • 时间复杂度：O(log(min(La, Lb)))，其中La和Lb分别是序列A和B的长度。这是因为在每一步中，我们都将输入规模减少一半。
    • 空间复杂度：O(1)，因为它只使用了一些变量来存储中间结果，而不需要额外的数据结构。
    • 备注：这段程序好像不能在网上的在线编译器跑，会显示“‘INT_MIN’ was not declared in this scope”。

     ⌨️优解代码

    1. #include 
    2. using namespace std;
    3.  
    4. // 函数：findMedianSortedArrays
    5. // 参数：两个升序数组A和B，以及它们的长度La和Lb
    6. // 返回值：两个数组的中位数
    7. double findMedianSortedArrays(int A[], int B[], int La, int Lb) {
    8.     // 确保La小于等于Lb，方便后续处理
    9.     if (La > Lb) {
    10.         swap(A, B);
    11.         swap(La, Lb);
    12.     }
    13.  
    14.     // 初始化左边界和右边界，以及两数组的中位数的位置（结果向下取整）
    15.     int left = 0, right = La;
    16.     int halfLen = (La + Lb + 1) / 2;
    17.  
    18.     // 使用二分查找在数组A中找到合适的位置
    19.     while (left < right) {
    20.         int i = left + (right - left) / 2;
    21.         int j = halfLen - i;
    22.  
    23.         int round = 1;
    24.         // cout << "Round " << round++ << ":" << endl;
    25.         // cout << "i = " << i << ", j = " << j << endl;
    26.  
    27.         // 通过比较A[i]和B[j-1]来调整i的位置
    28.         if (A[i] < B[j - 1])
    29.             left = i + 1;
    30.         else
    31.             right = i;
    32.  
    33.         // cout << "After comparison, left = " << left << ", right = " << right << endl << endl;
    34.     }
    35.  
    36.     // 计算中位数所在的位置
    37.     int i = left, j = halfLen - left;
    38.  
    39.     // 计算四个关键值，用于求解中位数
    40.     int AleftMax = (i == 0) ? INT_MIN : A[i - 1];   //如果i等于0（也就是A的左边界），那么将AleftMax设为整型的最小值 INT_MIN（通常是-2147483648）。否则，将AleftMax设为A中下标为i-1的元素的值。
    41.     int ArightMin = (i == La) ? INT_MAX : A[i];
    42.     int BleftMax = (j == 0) ? INT_MIN : B[j - 1];
    43.     int BrightMin = (j == Lb) ? INT_MAX : B[j];
    44.  
    45.     // cout << "Final values:" << endl;
    46.     // cout << "i = " << i << ", j = " << j << endl;
    47.     // cout << "AleftMax = " << AleftMax << ", ArightMin = " << ArightMin << endl;
    48.     // cout << "BleftMax = " << BleftMax << ", BrightMin = " << BrightMin << endl;
    49.  
    50.     // 根据数组总长度的奇偶性返回中位数
    51.     if ((La + Lb) % 2 == 1)
    52.         return max(AleftMax, BleftMax);
    53.     else
    54.         return (max(AleftMax, BleftMax) + min(ArightMin, BrightMin)) / 2.0;
    55. }
    56.  
    57. int main() {
    58.     int A[] = {11, 13, 15, 17, 19}; // 第一个升序数组
    59.     int B[] = {2, 4, 6, 8, 20};    // 第二个升序数组
    60.     int La = sizeof(A) / sizeof(A[0]); // 第一个数组的长度，将数组占用内存的总字节数除以第一个元素占用的字节数，我们得到了数组中元素的个数，也就是数组的长度。
    61.     int Lb = sizeof(B) / sizeof(B[0]); // 第二个数组的长度
    62.  
    63.     double median = findMedianSortedArrays(A, B, La, Lb); // 调用函数计算中位数
    64.  
    65.     cout << "中位数是: " << median << endl; // 输出中位数
    66.  
    67.     return 0;
    68. }

     ⌨️优解演算 

    • 初始：
      int A[] = {11, 13, 15, 17, 19};
      int B[] = {2, 4, 6, 8, 20};
      int La = 5;
      int Lb = 5;
      halfLen = (La + Lb + 1) / 2 = (5 + 5 + 1) / 2 = 11 / 2 = 5;
      left = 0;
      right = La = 5;

    • 第一轮循环：
      i = 0 + ( 5 - 0 ) / 2 = 2, j = 5 - 2 = 3;
      A[i = 2] = 15, B[j - 1 = 2] = 6;
      A[i] 大于 B[j - 1]，所以更新 right = i = 2

    • 第二轮循环：
      i = 0 + ( 2 - 0 ) / 2 = 1, j = 5 - 1 = 4;
      A[i = 1] = 13, B[4 - 1 = 3] = 8;
      A[i] 大于 B[j - 1]，所以更新 right = i = 1

    • 第三轮循环：
      i = 0 + ( 1 - 0 ) / 2 = 0, j = 5 - 0 = 5;
      A[i = 0] = 11, B[5 - 1 = 4] = 20;
      A[i] 小于 B[j - 1]，所以更新 left = j = 1

    • 不满足while循环条件，跳出:
      i = j = 1; j = 5-1 = 4;
      AleftMax = A[i-1] = 11, ArightMin = A[1] = 13；
      BleftMax = B[j-1] = 8, BrightMin = B[j] = 20；

      (La + Lb) % 2 = (5 + 5) % 2 = 10 % 2 = 0;
      max(AleftMax, BleftMax) + min(ArightMin, BrightMin)) / 2.0 = max(11+13)/2 =12

    🌰暴力解

    📇暴力解思路

    • 算法思想：将两个数组合并后排序，然后找到合并后数组的中位数；
    • 时间复杂度：O(La + Lb)；
    • 空间复杂度：O(La + Lb)；

    ⌨️暴力解代码

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. double findMedianSortedArrays(int A[], int B[], int La, int Lb) {
    6.     // 将数组A和数组B合并到一个新的数组C中
    7.     vector<int> C;
    8.     int i = 0, j = 0;
    9.     while (i < La && j < Lb) {
    10.         if (A[i] <= B[j]) {
    11.             C.push_back(A[i]);
    12.             i++;
    13.         } else {
    14.             C.push_back(B[j]);
    15.             j++;
    16.         }
    17.     }
    18.     while (i < La) {
    19.         C.push_back(A[i]);
    20.         i++;
    21.     }
    22.     while (j < Lb) {
    23.         C.push_back(B[j]);
    24.         j++;
    25.     }
    26.  
    27.     // 计算合并后数组C的长度
    28.     int Lc = C.size();
    29.  
    30.     // 计算中位数的位置
    31.     int mid = Lc / 2;
    32.  
    33.     if (Lc % 2 == 1) {
    34.         return C[mid];
    35.     } else {
    36.         return (C[mid - 1] + C[mid]) / 2.0;
    37.     }
    38. }
    39.  
    40. int main() {
    41.     int A[] = {11, 13, 15, 17, 19};
    42.     int B[] = {2, 4, 6, 8, 20};
    43.     int La = sizeof(A) / sizeof(A[0]);
    44.     int Lb = sizeof(B) / sizeof(B[0]);
    45.  
    46.     double median = findMedianSortedArrays(A, B, La, Lb);
    47.  
    48.     cout << "中位数是: " << median << endl;
    49.  
    50.     return 0;
    51. }

    ⌨️暴力解演算

    • int A[] = {11, 13, 15, 17, 19};  int B[] = {2, 4, 6, 8, 20};
    • vector C = {2, 4, 6, 8, 11, 13, 15, 17, 19};
      Lc = （C[4 ]+ C[5]）/2 = 12;

    🧵2013统考真题

    🧩题目

    已知一个整数序列A=（a0，a1，…，an）,其中0≤ai≤n。若存在ap1=ap2=…=apm=x 且 m > n/2 (0≤pk＜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。

    🌰优解 

    📇优解思路

    • 算法思想："摩尔投票算法"
      • 遍历数组并维护一个候选主元素以及一个计数器；
      • 在遍历过程中，如果计数器为零，就将当前元素设为候选主元素；否则，如果当前元素与候选主元素相同，计数器增加，否则计数器减少。最后剩下的候选主元素可能就是主元素；
      • 但还需要再次遍历数组确认它是否真的满足主元素的条件。
    • 时间复杂度：O(n)，其中n是输入数组的长度。算法需要进行两次遍历，每次遍历的时间复杂度都是O(n)。
    • 空间复杂度：O(1)，因为它只使用了常数级别的额外空间来存储候选主元素和计数器，而不随输入规模变化。

     ⌨️优解代码

    1. #include 
    2. using namespace std;
    3.  
    4. int findMajorityElement(int A[], int n) {
    5.     int candidate = -1;
    6.     int count = 0;
    7.  
    8.     // 第一轮遍历，选出候选主元素
    9.     for (int i = 0; i < n; i++) {
    10.         // cout << "candidate = A[" << i << "] = " << candidate << ", count = " << count << endl;
    11.         if (count == 0) {
    12.             candidate = A[i];
    13.             count = 1;
    14.         } else {
    15.             if (A[i] == candidate) {
    16.                 count++;
    17.             } else {
    18.                 count--;
    19.             }
    20.         }
    21.     }
    22.  
    23.     // 第二轮遍历，确认候选主元素是否真的是主元素
    24.     count = 0;
    25.     for (int i = 0; i < n; i++) {
    26.         if (A[i] == candidate) {
    27.             count++;
    28.         }
    29.     }
    30.  
    31.     // cout << "count = " << count << endl;
    32.     if (count > n / 2) {
    33.         return candidate;
    34.     } else {
    35.         return -1;
    36.     }
    37. }
    38.  
    39. int main() {
    40.     int A[] = {0, 5, 5, 3, 5, 7, 5, 5};
    41.     int B[] = {0, 5, 5, 3, 5, 1, 5, 7};
    42.     int La = sizeof(A) / sizeof(A[0]);
    43.     int Lb = sizeof(B) / sizeof(B[0]);
    44.  
    45.     int resultA = findMajorityElement(A, La);
    46.     int resultB = findMajorityElement(B, Lb);
    47.  
    48.     if (resultA != -1) {
    49.         cout << "数组A的主元素是：" << resultA << endl;
    50.     } else {
    51.         cout << "数组A没有主元素" << endl;
    52.     }
    53.  
    54.     if (resultB != -1) {
    55.         cout << "数组B的主元素是：" << resultB << endl;
    56.     } else {
    57.         cout << "数组B没有主元素" << endl;
    58.     }
    59.  
    60.     return 0;
    61. }

     ⌨️优解演算 

    • 数组A
      candidate = A[0] = -1, count = 0
      candidate = A[1] = 0, count = 1
      candidate = A[2] = 0, count = 0
      candidate = A[3] = 5, count = 1
      candidate = A[4] = 5, count = 0
      candidate = A[5] = 5, count = 1
      candidate = A[6] = 5, count = 0
      candidate = A[7] = 5, count = 1
      count = 5，count ＞ 8/2

    • 数组B
      candidate = A[0] = -1, count = 0
      candidate = A[1] = 0, count = 1
      candidate = A[2] = 0, count = 0
      candidate = A[3] = 5, count = 1
      candidate = A[4] = 5, count = 0
      candidate = A[5] = 5, count = 1
      candidate = A[6] = 5, count = 0
      candidate = A[7] = 5, count = 1
      count = 4，count ≤ 8/2

    🌰暴力解

    📇暴力解思路

    • 算法思想：
      • 统计每种元素的出现次数，然后找到出现次数最多的元素。
      • 第一遍遍历数组，统计每种元素的出现次数，可以使用一个哈希表或者数组来存储。
      • 第二遍遍历统计结果，找到出现次数最多的元素。
      • 检查该元素的出现次数是否大于总长度除以2，如果满足条件，则它是主元素，否则不存在主元素。
    • 时间复杂度：O(n)，其中n是输入数组的长度。
    • 空间复杂度：O(n)，取决于不同元素的数量，最坏情况下可能会达到O(n)。

    ⌨️暴力解代码

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. int findMajorityElement(int A[], int n) {
    6.     // 使用哈希表 counter 统计每个元素的出现次数
    7.     unordered_map<int, int> counter;
    8.  
    9.     // 第一次遍历，统计每个元素的出现次数
    10.     for (int i = 0; i < n; i++) {
    11.         counter[A[i]]++;
    12.     }
    13.  
    14.     // 测试：输出哈希表的值
    15.     // cout << "Counter:" << endl;
    16.     // for (auto& pair : counter) {
    17.     //     cout << pair.first << ": " << pair.second << endl;
    18.     // }
    19.  
    20.     // 找到出现次数最多的元素
    21.     int maxCount = 0;
    22.     int majorityElement = -1;
    23.  
    24.     for (auto& pair : counter) {           // 声明一个名为 pair 的变量，它的类型会根据 counter 中的元素类型自动推断（因为我们使用了 auto）。pair 实际上是一个键值对，包括一个键（pair.first）和一个值（pair.second）。
    25.  
    26.         // 测试：输出所有参数的值
    27.         // cout << "pair.first = " << pair.first << ", pair.second = " << pair.second << endl;
    28.         // cout << "maxCount = " << maxCount << ", majorityElement = " << majorityElement << endl;
    29.  
    30.         if (pair.second > maxCount) {       // 比较当前键值对的值（也就是元素出现的次数 pair.second）和 maxCount 的大小
    31.             maxCount = pair.second;         // 如果当前元素出现的次数大于 maxCount，则更新 maxCount 和 majorityElement
    32.             majorityElement = pair.first;   // 将当前元素作为候选主元素
    33.         }
    34.     }
    35.  
    36.  
    37.     // 检查出现次数是否大于总长度的一半
    38.     if (maxCount > n / 2) {
    39.         return majorityElement;
    40.     } else {
    41.         return -1;
    42.     }
    43. }
    44.  
    45. int main() {
    46.     int A[] = {0, 5, 5, 3, 5, 7, 5, 5};
    47.     int B[] = {0, 5, 5, 3, 5, 1, 5, 7};
    48.     int La = sizeof(A) / sizeof(A[0]);
    49.     int Lb = sizeof(B) / sizeof(B[0]);
    50.  
    51.     int resultA = findMajorityElement(A, La);
    52.     int resultB = findMajorityElement(B, Lb);
    53.  
    54.     if (resultA != -1) {
    55.         cout << "数组A的主元素是：" << resultA << endl;
    56.     } else {
    57.         cout << "数组A没有主元素" << endl;
    58.     }
    59.  
    60.     if (resultB != -1) {
    61.         cout << "数组B的主元素是：" << resultB << endl;
    62.     } else {
    63.         cout << "数组B没有主元素" << endl;
    64.     }
    65.  
    66.     return 0;
    67. }

    ⌨️暴力解演算

    • 数组A模拟：
      Counter:
      3: 1
      7: 1
      0: 1
      5: 5
      pair.first = 3, pair.second = 1
      maxCount = 0, majorityElement = -1
      pair.first = 7, pair.second = 1
      maxCount = 1, majorityElement = 3
      pair.first = 0, pair.second = 1
      maxCount = 1, majorityElement = 3
      pair.first = 5, pair.second = 5
      maxCount = 1, majorityElement = 3
      数组A的主元素是：5

    • 数组B模拟：
      Counter:
      1: 1
      3: 1
      7: 1
      0: 1
      5: 4
      pair.first = 1, pair.second = 1
      maxCount = 0, majorityElement = -1
      pair.first = 3, pair.second = 1
      maxCount = 1, majorityElement = 1
      pair.first = 7, pair.second = 1
      maxCount = 1, majorityElement = 1
      pair.first = 0, pair.second = 1
      maxCount = 1, majorityElement = 1
      pair.first = 5, pair.second = 4
      maxCount = 1, majorityElement = 1
      数组B没有主元素

    🧵2018统考真题

    🧩题目

    给定一个含n个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1，数组{1,2,3}中未出现的最小正整数是4。

    🌰优解 

    📇优解思路

    • 算法思想："哈希表标记"
      • 利用数组本身来进行标记，将数组元素放置到其对应的位置上；
      • 然后再遍历一次数组找出第一个不符合规则的位置，即未出现的最小正整数。
    • 时间复杂度：O(n)，因为最多需要遍历两次数组。
    • 空间复杂度：O(n)，使用了一个大小与输入数组相同的数组进行操作，因此空间复杂度是线性的，与输入数组的大小成正比。
    • 备注：这个算法思想应该还是挺容易想到的，因此没有暴力解。

     ⌨️优解代码

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. int firstMissingPositive(vector<int>& nums) {
    6.     int n = nums.size();
    7.  
    8.     // 将数组元素放置到其对应的位置上
    9.     for (int i = 0; i < n; ++i) {
    10.         while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
    11.             swap(nums[i], nums[nums[i] - 1]);
    12.         }
    13.     }
    14.  
    15.     // 再次遍历数组，找出第一个不符合规则的位置
    16.     for (int i = 0; i < n; ++i) {
    17.         if (nums[i] != i + 1) {
    18.             return i + 1;
    19.         }
    20.     }
    21.  
    22.     return n + 1; // 如果数组本身符合规则，则返回数组长度加1
    23. }
    24.  
    25. int main() {
    26.     vector<int> arr1 = {-5, 3, 2, 3};
    27.     vector<int> arr2 = {1, 2, 3};
    28.  
    29.     int missing1 = firstMissingPositive(arr1);
    30.     int missing2 = firstMissingPositive(arr2);
    31.  
    32.     cout << "数组{-5, 3, 2, 3}中未出现的最小正整数是：" << missing1 << endl;
    33.     cout << "数组{1, 2, 3}中未出现的最小正整数是：" << missing2 << endl;
    34.  
    35.     return 0;
    36. }

    🧵2020统考真题

    🧩题目

    定义三元组(a,b,c)(a,b,c均为整数)的距离D=|a-b| + |b-c| + |c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能得三元组(a,b,c)(a∈S1，b∈S2，c∈S3)中的最小距离、例如S1={-1,0,9}，S2={-25,-10,-10,11}，S3={2,9,17,30,41}，则最小距离为2，相应的三元组为(9,10,9)。

    🌰优解 

    📇优解思路

    • 通用思路：在求解距离的问题中，通常的做法是通过遍历或者适当的比较来不断更新最小值。这种方法通常会在处理多个元素之间的关系时有效，尤其是在找到最小值或最大值时。
    • 算法思想：
      • 选择S1、S2和S3中的一个数作为其中一个元素（比如选择S1中的元素作为a）；
      • 然后在S2和S3中使用两个指针分别找到与a最接近的b和c，从而计算距离，并维护最小距离；
    • 时间复杂度：O(n)，emm...如果忽略那段蠢萌的vector输出的话；
    • 空间复杂度：O(1)，除了用于存储输入数组外，算法中没有使用额外的辅助空间。

     ⌨️优解代码

    1. #include 
    2. #include 
    3. #include   // 在本示例中，INT_MAX 和 INT_MIN 分别用于初始化最小距离变量为最大可能值，以便在计算距离时进行比较，并找到最小值。
    4. using namespace std;
    5.  
    6. int minDistanceTriplet(vector<int>& S1, vector<int>& S2, vector<int>& S3) {
    7.     int minDistance = INT_MAX;
    8.     int i = 0, j = 0, k = 0;
    9.     int size1 = S1.size(), size2 = S2.size(), size3 = S3.size();
    10.  
    11.     while (i < size1 && j < size2 && k < size3) {
    12.         int a = S1[i], b = S2[j], c = S3[k];
    13.         int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);
    14.         minDistance = min(minDistance, currentDistance);
    15.  
    16.         // 找到与当前 a 最接近的 b
    17.         if (a <= b && a <= c) {
    18.             i++;
    19.         } else if (b <= a && b <= c) {
    20.             j++;
    21.         } else {
    22.             k++;
    23.         }
    24.     }
    25.  
    26.     return minDistance;
    27. }
    28.  
    29. void printTriplet(int a, int b, int c) {
    30.     cout << "三元组为: (" << a << ", " << b << ", " << c << ")" << endl;
    31. }
    32.  
    33. int main() {
    34.     vector<int> S1 = {-1, 0, 9};
    35.     vector<int> S2 = {-25, -10, 10, 11};
    36.     vector<int> S3 = {2, 9, 17, 30, 41};
    37.  
    38.     int minDist = minDistanceTriplet(S1, S2, S3);
    39.  
    40.     cout << "最小距离为: " << minDist << endl;
    41.  
    42.     // 输出三元组
    43.     // 遍历三元组的索引，根据索引取得对应元素输出
    44.     for (int i = 0; i < S1.size(); ++i) {
    45.         for (int j = 0; j < S2.size(); ++j) {
    46.             for (int k = 0; k < S3.size(); ++k) {
    47.                 int a = S1[i], b = S2[j], c = S3[k];
    48.                 int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);
    49.                 if (currentDistance == minDist) {
    50.                     printTriplet(a, b, c);
    51.                 }
    52.             }
    53.         }
    54.     }
    55.  
    56.     return 0;
    57. }

    🌰暴力解

    📇暴力解思路

    • 算法思想：
      • 使用三重循环来遍历所有可能的三元组；
      • 计算每个三元组的距离并更新最小值；
    • 时间复杂度：O(n)，其中n是输入数组的长度；
    • 空间复杂度：O(1)。

    ⌨️暴力解代码

    1. #include 
    2. #include 
    3. #include   // 在本示例中，INT_MAX 和 INT_MIN 分别用于初始化最小距离变量为最大可能值，以便在计算距离时进行比较，并找到最小值。
    4. using namespace std;
    5.  
    6. int minDistanceTriplet(vector<int>& S1, vector<int>& S2, vector<int>& S3) {
    7.     int minDistance = INT_MAX;
    8.     for (int i = 0; i < S1.size(); ++i) {
    9.         for (int j = 0; j < S2.size(); ++j) {
    10.             for (int k = 0; k < S3.size(); ++k) {
    11.                 int a = S1[i], b = S2[j], c = S3[k];
    12.                 int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);
    13.                 minDistance = min(minDistance, currentDistance);
    14.             }
    15.         }
    16.     }
    17.     return minDistance;
    18. }
    19.  
    20.  
    21. void printTriplet(int a, int b, int c) {
    22.     cout << "三元组为: (" << a << ", " << b << ", " << c << ")" << endl;
    23. }
    24.  
    25. int main() {
    26.     vector<int> S1 = {-1, 0, 9};
    27.     vector<int> S2 = {-25, -10, 10, 11};
    28.     vector<int> S3 = {2, 9, 17, 30, 41};
    29.  
    30.     int minDist = minDistanceTriplet(S1, S2, S3);
    31.  
    32.     cout << "最小距离为: " << minDist << endl;
    33.  
    34.     // 输出三元组
    35.     // 遍历三元组的索引，根据索引取得对应元素输出
    36.     for (int i = 0; i < S1.size(); ++i) {
    37.         for (int j = 0; j < S2.size(); ++j) {
    38.             for (int k = 0; k < S3.size(); ++k) {
    39.                 int a = S1[i], b = S2[j], c = S3[k];
    40.                 int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);
    41.                 if (currentDistance == minDist) {
    42.                     printTriplet(a, b, c);
    43.                 }
    44.             }
    45.         }
    46.     }
    47.  
    48.     return 0;
    49. }

    🔚结语

    博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~😶‍🌫️

    我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，收到点赞的话，博主肝文的动力++~🌟🌟

    数据结构_梅头脑_的博客-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/weixin_42789937/category_12262100.html?spm=1001.2014.3001.5482

  • 相关阅读:
    spring源码下载安装，导入idea以及编译报错问题详细解决过程
    Nginx的相关库简介
    【面试普通人VS高手系列】讲一下wait和notify这个为什么要在synchronized代码块中？
    大语言模型的原理
    区块链技术在金融领域的应用场景
    并发编程（二）原子性和Synchronized同步锁
    Pytorch模型训练实用教程学习笔记：四、优化器与学习率调整
    记ZooKeeper3.7在win下的单机部署
    竞赛 基于大数据的社交平台数据爬虫舆情分析可视化系统
    serveless 思想 Midway.js 框架使用教程（七）
  • 原文地址：https://blog.csdn.net/weixin_42789937/article/details/134471464