辽宁网站制作公司,潍坊网站建设维护,塘厦在哪里,企业画册vi设计在之间的两篇文章中#xff0c;我们着重讲了顺序表及顺序表的实现。今天这篇文章我们将简单讲解关于顺序表的三个算法题。这三个题也都属于力扣上的经典例题。1.例题1:移除元素例题来源(力扣) : https://leetcode.cn/problems/remove-element/description/这是一道数组操作算法…在之间的两篇文章中我们着重讲了顺序表及顺序表的实现。今天这篇文章我们将简单讲解关于顺序表的三个算法题。这三个题也都属于力扣上的经典例题。1.例题1:移除元素 例题来源(力扣) : https://leetcode.cn/problems/remove-element/description/这是一道数组操作算法题核心任务是
可以简单理解为 : 给你一个装着数字的“盒子”数组 nums 和一个特定数字 val 要你在这个“盒子”里直接把所有等于 val 的数字去掉并且把剩下的数字往前排最后告诉别人剩下多少个
不等于 val 的数字返回 k 。
比如盒子里是 [3,2,2,3] 要去掉 3操作后盒子前两位变成 [2,2] 返回剩下 2 个。
方法一 : 嵌套循环移位法int removeElement(int* nums, int numsSize, int val)
{int i,j;for(i 0;inumsSize; ){if(nums[i]val){// 当找到要移除的元素时将后面元素逐个向前移位for(j i;jnumsSize-1;j) {nums[j] nums[j1];}numsSize--; //覆盖掉当前要移除的元素同时将数组有效长度numsSize减1}else{i; }}return numsSize;
}思路:- 外层 for 循环遍历数组循环条件中 i 不直接自增根据元素是否等于 val 决定后续操作。- 当发现 nums[i] 等于 val 时通过内层 for 循环将 i 位置之后的所有元素依次向前移动一位覆盖掉当前要移除的元素同时将数组有效长度 numsSize 减 1若 nums[i] 不等于val则 i 正常自增继续遍历下一个元素。- 最终返回的 numsSize 就是数组中不等于 val 的元素数量且数组前 numsSize 个元素已更新为不含 val 的结果。
时间复杂度
- 最坏情况下根据两个 for 循环, 可以得出时间复杂度为 O(n^2) 其中 n 是数组 nums 的初始长度 。- 最好情况下数组中没有等于 val 的元素外层循环只需遍历一次数组时间复杂度为O(n) 。取最坏的结果所以第一种解法的时间复杂度为 O(n^2)。
空间复杂度- 整个过程只使用了有限的几个额外变量 i 、 j 等 没有额外开辟大量数据存储空间空间复杂度为 O(1) 属于原地操作。方法二 : 借助数组法int removeElement(int* nums, int numsSize, int val)
{// 动态分配一个与原数组大小相同的临时数组处理 numsSize 为 0 的情况避免非法int* tmp (int*)malloc(numsSize * sizeof(int)); if(tmp NULL){return 0;}int index 0; // 记录新数组 tmp 的下标用于存放不等于 val 的元素for(int i 0;inumsSize;i){if(nums[i]!val){tmp[index] nums[i];index;}}// 将临时数组中有效元素不等于 val 的元素拷贝回原数组前 index 个位置for(int i 0;iindex;i){nums[i] tmp[i];}free(tmp); // 释放临时数组内存避免内存泄漏return index;
}思路
- 首先动态分配一个和原数组 nums 大小相同的临时数组 tmp用于存储不等于 val 的元素。若内存分配失败 tmp NULL 直接返回 0。
- 遍历原数组 nums 当遇到元素不等于 val 时将其存入临时数组 tmp 中同时用 index 记录 tmp 中有效元素的个数即下标 。
- 遍历结束后把临时数组 tmp 中存储的有效元素共 index 个 拷贝回原数组nums 的前 index 个位置最后释放临时数组 tmp 的内存避免内存泄漏返回 index 即原数组中不等于 val 的元素数量。
时间复杂度
- 遍历原数组 nums 是一个 O(n) 的操作 n 为数组初始长度 numsSize 将临时数组元素拷贝回原数组也是一个 O(k) 的操作 k 为不等于 val 的元素数量最大为 n 总的时间复杂度为 O(n) 因为 O(n k) 中 k 最大不超过 n 可简化为 O(n) 。
空间复杂度
- 额外动态分配了一个大小为 numsSize 的临时数组 tmp 所以空间复杂度为 O(n) 。我们可以明确的观察到第二种方法的时间复杂度比第一种方法的时间复杂度更简单但是空间复杂度比第一种解法的空间复杂度更复杂所以第二种方法比第一种方法就是采用了空间换时间的做法方法三 : 双指针法推荐的高效原地算法 int removeElement(int* nums, int numsSize, int val)
{int dst 0,src 0; while(src numsSize){// 当 src 指向元素不等于 val 时将其赋值到 dst 位置dst 后移if(nums[src] ! val) {nums[dst] nums[src];dst;}src; }return dst;
}思路
- 定义两个指针这里用变量 dst 和 src 模拟指针功能 src 用于遍历原数组 nums 逐个检查元素 dst 用于标记新数组即处理后不含 val 的数组部分 的最后一个位置。
- 遍历过程中当 nums[src] 不等于 val 时说明该元素是需要保留的将其赋值到nums[dst] 的位置然后 dst 自增 1指向下一个要填充的位置不管 nums[src] 是否等于 val src 都要自增 1 继续遍历下一个元素。
- 当 src 遍历完整个数组 src numsSize 时 dst 的值就是原数组中不等于 val 的元素数量且原数组前 dst 个元素已经是处理后不含 val 的结果。
时间复杂度
- 只需遍历一次原数组 nums src 从 0 走到 numsSize - 1 循环执行 numsSize 次所以时间复杂度为 O(n) 其中 n 是数组 nums 的初始长度 。
空间复杂度
- 只使用了常数个额外变量 dst 、 src 没有额外开辟大量数据存储空间空间复杂度为 O(1) 属于高效的原地算法。通过第三种方法我们可以观察到第三种方法比前两种方法都更加简单。时间复杂度比第一种方法更简单空间复杂度比第二种方法更简单。在实际开发中优先推荐 双指针法 它在时间和空间复杂度上都更优能高效解决问题嵌套循环移位法在数据量小的时候可以用但数据量大时性能不佳借助额外数组法一般不是最优选择除非有特殊场景需求比如不能修改原数组内容只是临时拷贝处理等但本题要求原地操作它其实不太契合题目 “原地” 要求只是一种思路 。2.例题2:删除有序数组中的重复项
例题来源(力扣) : https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
这道题也可以使用双指针的解题方法来写。并且使用双指针能够最大程度的简化时间和空间复杂度。下面我们来看一下双指针的具体解法。给非严格递增有序数组 nums 原地删除重复元素使每个元素仅出现一次保持相对顺序返回新长度 k 且需保证 nums 前 k 个元素为去重后的唯一元素。方法 : 双指针解法int removeDuplicates(int* nums, int numsSize) {// dst 初始指向第 1 个唯一元素应在的位置初始为 0int dst 0, src dst 1; // src 遍历整个数组找后续元素while (src numsSize) { // 条件 1当前 src 元素与 dst 元素不同需保留 src 元素// 条件 2dst ! src尝试移动 dst 后判断是否与 src 位置重叠if (nums[src] ! nums[dst] dst ! src) { // 将 src 元素放到 dst 位置保证前 dst1 个元素唯一nums[dst] nums[src]; }// src 继续向后遍历src; }// dst 是最后一个唯一元素的下标长度为下标 1return dst 1;
}思路以 nums [1,1,2] 为例 :
1. 初始状态 dst 0 指向第一个 1 src 1 指向第二个 1 。2. 第一次循环 nums[src] nums[dst] 都是 1 足 nums[src]!nums[dst] src →src 2 。3. 第二次循环 nums[src] 2 ≠ nums[dst] 1 执行 dst dst 1 判断 dst !src 1 ! 2 → 成立 执行 nums[1] 2 数组变为 [1,2,2] src → src 3 退出循环 。4. 返回结果 dst 1 2 与题目要求一致。
复杂度分析:
时间复杂度:
- 核心逻辑 src 从 1 遍历到 numsSize - 1 仅遍历数组一次。- 无论数组多长循环次数为 numsSize - 1 src 移动次数 因此时间复杂度为 O(n) n 为numsSize 即数组长度 。
空间复杂度:
- 函数仅使用 dst 、 src 两个额外变量未动态分配内存如 malloc 。- 额外空间占用与数组长度无关始终为常数因此空间复杂度为 O(1) 原地算法 。对于本地来说双指针法就是最优的解法。无论是从时间复杂度还是从空间复杂度来说都是最优答案。希望大家能够好好理解这道题好好理解双指针的方法。3.例题3:合并两个有序数组例题来源(力扣) : https://leetcode.cn/problems/merge-sorted-array/description/这道题的大概思路 : 给你两个已经排好序非递减即从小到大的数组 nums1 和 nums2 但nums1 后面有额外的空间题目里说 nums1 初始长度是 m n 前 m 个是有效元素后 n 个是闲置的 0 。你需要把 nums2 的元素合并到 nums1 里并且合并后整个 nums1 仍然保持非递减顺序最后结果直接存在 nums1 里不用返回新数组。这道题有三种解法。下面我们一一来看。方法一 : 先合并再冒泡排序void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{// 1. 合并 nums2 到 nums1 中int k 0;for (int i m; i m n; i) {nums1[i] nums2[k];k;}// 2. 冒泡排序实现升序排列int len m n;for (int i 0; i len - 1; i) {for (int j 0; j len - i - 1; j) {if (nums1[j] nums1[j 1]) {// 交换元素int temp nums1[j];nums1[j] nums1[j 1];nums1[j 1] temp;}}}
}思路:- 合并阶段利用循环把 nums2 中的元素依次放到 nums1 中原本后面闲置的位置即从下标 m 开始的位置 完成两个数组合并为一个数组的操作。
- 排序阶段采用冒泡排序对合并后的 nums1 数组长度为 m n 进行升序排序通过相邻元素比较和交换让整个数组有序。
复杂度分析
- 时间复杂度合并操作是 O(n) n 是 nums2 的长度 冒泡排序的时间复杂度是 O((m n)²) 。总的时间复杂度由冒泡排序主导为 O((m n)²) 因为 (m n)² 增长速度比 n 快得多。
- 空间复杂度整个过程只用到了几个临时变量如 k 、 i 、 j 、 temp 等 没有额外开辟大量数据存储空间空间复杂度是 O(1) 。如果大家不懂冒泡排序的话小编之前在c语言的讲解中详细讲解了冒泡排序的逻辑以及代码内容。有兴趣的可以去看一下。方法二 : 先合并再快速排序借助 qsort 排序法)// 比较函数用于 qsort实现升序排序
int compare(const void *a, const void *b)
{return (*(int *)a - *(int *)b);
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{// 1. 合并 nums2 到 nums1 中int k 0;for (int i m; i m n; i) {nums1[i] nums2[k];k;}// 2. 使用 qsort 对合并后的 nums1 进行升序排序qsort(nums1, m n, sizeof(int), compare);
}思路
- 合并阶段和方法一一样通过循环将 nums2 的元素放到 nums1 后面的闲置位置完成合并。
- 排序阶段调用标准库函数 qsort 对合并后的 nums1 数组进行升序排序。 qsort 内部一般采用快速排序算法优化版本平均情况高效 根据自定义的 compare 比较函数返回 a - b 实现升序 来排序。
复杂度分析
- 时间复杂度合并操作时间复杂度是 O(n) 。 qsort 基于快速排序平均时间复杂度是 O((m n)log(m n)) 最坏情况比如数组完全有序等极端情况快速排序退化为冒泡排序逻辑但实际 qsort 有优化一般不考虑 时间复杂度是 O((m n)²) 这里按平均情况总的时间复杂度由 qsort 主导为 O((m n)log(m n)) 。
- 空间复杂度合并阶段空间复杂度 O(1) qsort 内部实现可能会用到递归栈或者额外的辅助空间不过空间复杂度平均情况是 O(log(m n)) 递归栈深度 最坏情况是 O(m n) 但整体相对于方法一在排序环节更高效。qsort排序小编之前也在c语言的相关内容中讲解过有兴趣的可以去了解一下。方法三 : 双指针从后往前合并void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int l1 m - 1; // nums1 中有效元素即原本要合并的元素的最后一个下标int l2 n - 1; // nums2 中元素的最后一个下标int l3 m n - 1; // 合并后 nums1 数组的最后一个下标// 同时遍历 nums1 和 nums2 的有效元素从后往前while (l1 0 l2 0) {if (nums1[l1] nums2[l2]) {// nums1 当前元素更大放到合并后数组的当前最后位置nums1[l3--] nums1[l1--];} else {// nums2 当前元素更大或相等放到合并后数组的当前最后位置nums1[l3--] nums2[l2--];}}// 如果 nums2 还有剩余元素说明 nums1 有效元素已经处理完了直接放到 nums1 前面位置while (l2 0) {nums1[l3--] nums2[l2--];}
}思路
- 利用三个指针 l1 指向 nums1 中原有有效元素的末尾 l2 指向 nums2 元素的末尾 l3 指向合并后 nums1 数组的末尾。
- 从后往前比较 nums1 和 nums2 中的元素把较大的元素放到 nums1 中 l3 指向的位置然后对应的指针向前移动。
- 当 nums1 原有有效元素处理完 l1 0 如果 nums2 还有剩余元素 l2 0 直接把这些元素依次放到 nums1 中剩下的位置因为 nums2 本身是有序的这样就能保证合并后整体有序。
复杂度分析
- 时间复杂度整个过程中 l1 从 m - 1 往前遍历到 -1 l2 从 n - 1 往前遍历到 -1 l3 从 m n - 1 往前遍历到 -1 总的操作次数是 m n 次所以时间复杂度是 O(m n) 。
- 空间复杂度只用到了几个指针变量 l1 、 l2 、 l3 没有额外开辟大量数据存储空间空间复杂度是 O(1) 。在实际应用中双指针法方法三 是最优解充分利用了数组有序的条件时间和空间复杂都更优方法一仅适合理解排序和合并逻辑实际很少用方法二借助库函数简化了排序实现但效率不如方法三且依赖库 。好了以上就是关于顺序表部分有关算法题的内容。这些题都运用了一个共同的方法那就是双指针法。双体执法在后面的算法题中属于非常重要且非常常见的一种算术方法大家一定要了解并且熟练掌握它。
以后小编也会更新一些常见的算法题和一些比较重要的算法方法。喜欢的可以给小编留个关注感谢大家的观看。
