误闯天家！数据结构-线性表王道经典例题剖析
个人主页-爱因斯晨
文章专栏-数据结构
文章目录
学了数据结构才是真正的误闯天家啊！博主一学数据结构就难受，浑身难受…博主宁愿积分也不想学数据结构
一、基础操作：元素删除与查找
1. 删除最小值元素
题目：从顺序表中删除具有最小值的元素（假设唯一），并返回被删元素值，空出位置由最后一个元素填补。
思路：遍历找最小值位置，再用最后一个元素覆盖，调整表长。
// 假设顺序表用数组存储，len 记录长度int delMin(int arr[], int *len) { if (*len == 0) return -1; // 表空处理 int minVal = arr[0], minIndex = 0; for (int i = 1; i < *len; i++) { if (arr[i] < minVal) { minVal = arr[i]; minIndex = i; } } arr[minIndex] = arr[--(*len)]; // 最后一个元素填补 return minVal;}复杂度：遍历找最小值是 O (n)，元素移动是 O (1)，整体时间 O (n)；空间 O (1)，没额外开大量空间。
2. 删除所有值为 x 的元素（O (n) 时间 + O (1) 空间）
题目：高效删除顺序表中所有值为 x 的元素。
思路：双指针，i 遍历找非 x 元素，j 记录存储位置，把非 x 元素往前挪，最后调整表长。
void delAllX(int arr[], int *len, int x) { int j = 0; for (int i = 0; i < *len; i++) { if (arr[i] != x) { arr[j++] = arr[i]; } } *len = j;}复杂度：一次遍历 O (n)，空间 O (1)，用双指针优化，避免多次移动元素，比嵌套循环高效。
二、进阶玩法：融合与特殊逻辑
1. 合并两个有序顺序表
题目：把两个有序顺序表合并成新的有序表。
思路：双指针遍历两个表，比大小依次放入新表，类似归并排序的归并步骤。
// 假设 a、b 是有序表，lenA、lenB 是长度，res 存结果void mergeOrdered(int a[], int lenA, int b[], int lenB, int res[]) { int i = 0, j = 0, k = 0; while (i < lenA && j < lenB) { if (a[i] < b[j]) { res[k++] = a[i++]; } else { res[k++] = b[j++]; } } // 处理剩余元素 while (i < lenA) res[k++] = a[i++]; while (j < lenB) res[k++] = b[j++];}复杂度：遍历两个表，时间 O (lenA + lenB)；空间用了额外数组存结果，若算输出空间是 O (lenA + lenB)，不算的话是 O (1) 辅助空间。
2. 找三个有序数组都不包含的元素
题目：给三个有序数组，找出同时不在这三个数组里的元素。
思路：三指针遍历，标记已检查位置，比较元素，跳过重复，逐步找目标。比如数组 A[1,2,3]、B[2,3,4]、C[-1,0,2]，要找出都不出现的数。
// 简化版，假设找最小的不出现元素，实际需遍历所有可能int findNotInThree(int A[], int lenA, int B[], int lenB, int C[], int lenC) { int i = 0, j = 0, k = 0; int maxVal = 0; // 先找三个数组最大值，确定遍历范围 // 省略找 maxVal 逻辑... for (int num = 0; num <= maxVal; num++) { // 检查是否在 A、B、C 中 while (i < lenA && A[i] < num) i++; while (j < lenB && B[j] < num) j++; while (k < lenC && C[k] < num) k++; if (i >= lenA || A[i] != num) if (j >= lenB || B[j] != num) if (k >= lenC || C[k] != num) return num; } return -1; // 假设都存在返回 -1，实际按需调整}复杂度：遍历到最大值，时间 O (max (lenA, lenB, lenC) + maxVal) ，若 maxVal 是合理范围（比如由数组元素决定 ），可接受；空间 O (1) 。
三、特殊逻辑：循环移位与主元素
1. 数组循环左移
题目：把数组循环左移 p 个位置，比如 [X₀,X₁,...Xₙ₋₁] 变 [Xp,Xp+1,...Xₙ₋₁,X₀,X₁,...Xp-1]。
思路：三次逆置！先逆置前 p 个，再逆置后 n - p 个，最后整体逆置，避免逐个移动元素。
// 逆置函数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 leftShift(int arr[], int n, int p) { p %= n; // 处理 p 超过长度情况 reverse(arr, 0, p - 1); reverse(arr, p, n - 1); reverse(arr, 0, n - 1);}复杂度：三次逆置，每次最多 O (n/2) 操作，整体时间 O (n) ；空间 O (1) ，纯原地操作。
2. 找主元素（出现次数超一半）
题目：判断数组是否有主元素（出现次数 > n/2 ），有则输出，无则输出 -1。
思路：摩尔投票法！遍历数组，遇到相同元素计数 +1，不同则 -1，最后验证剩余元素是否真为主元素。
int findMajor(int arr[], int len) { int candidate = arr[0], count = 1; for (int i = 1; i < len; i++) { if (arr[i] == candidate) { count++; } else { count--; if (count == 0) { candidate = arr[i]; count = 1; } } } // 验证 count = 0; for (int i = 0; i < len; i++) { if (arr[i] == candidate) count++; } return count > len / 2 ? candidate : -1;}复杂度：两次遍历数组，时间 O (n) ；空间 O (1) ，用常数变量存候选和计数。
四、总结：顺序表解题核心
这些题围绕顺序表的遍历、元素移动、指针（索引）技巧展开，关键是：
- 利用顺序表随机访问：通过索引快速定位、操作元素，比如找最小值、双指针遍历。
- 优化时间 / 空间复杂度：能用 O (1) 辅助空间就不用额外数组（如双指针、摩尔投票 ）；用遍历、逆置等操作把时间压到 O (n) 。
核心
这些题围绕顺序表的遍历、元素移动、指针（索引）技巧展开，关键是：
- 利用顺序表随机访问：通过索引快速定位、操作元素，比如找最小值、双指针遍历。
- 优化时间 / 空间复杂度：能用 O (1) 辅助空间就不用额外数组（如双指针、摩尔投票 ）；用遍历、逆置等操作把时间压到 O (n) 。
- 理解算法本质：像循环移位的三次逆置，是用 “局部逆置 + 整体逆置” 实现循环效果；摩尔投票法利用计数抵消找可能主元素，这些思路能迁移到其他场景。
