网站的配色方案百度秒收录技术最新
目录
一、顺序表算法题
1、移除元素
2、删除有序数组中的重复项
3、 合并两个有序数组
二、顺序表问题与思考
一、顺序表算法题
1、移除元素
移除元素 - 力扣（LeetCode）
思路分析：
思路一：创建一个新数组，开辟新空间，把符合条件的元素放到新数组中，再释放和销毁旧空间。
思路二：用顺序表査找指定元素，并返回该指定元素的下标，再删除指定下标的位置。
思路三：用一个顺序表查找指定元素，逐个查找指定元素，与符合条件的元素删除，后面往前挪动一个位置。
我们现在以思路三来详细分析一下：
第一层循环：遍历数组，查找val。
第二层循环：val之后的数据整体往前挪动一位。
时间复杂度为O(n^2)，对于需要查找多次的复杂算法题比较不友好，运行时间长；
但对于这一道带提示条件的简单算法题，就没有时间限制的要求，所以就无需关心时间复杂度。
但对于追求更高要求的时间和空间的相关算法复杂度的精度，我们从以下思路来入手：
最终思路：
该思路的时间复杂度为O(n)；空间复杂度为O(1)。
定义两个变量指向数组第一个位置，判断nums[src]是否等于val，所以有以下两者情况：
（1）当nums[src]等于val，所以src++；
（2）当nums[src]不等于val，所以nums[dst]=nums[src]，src++，dst++。
我们就这个数组例子来分析一下：
（1）因为nums[src]等于val，所以src++；当src++后，nums[src]为数组第二个元素的位置，nums[src]不等于val，nums[dst]=nums[src]，此时数组第一个元素被赋值为2，再src++，dst++。
（2） 当src++和dst++后，nums[src]为数组第三个元素的位置，nums[sdst]为数组第二个元素的位置。nums[src]不等于val，nums[dst]=nums[src]，此时数组第二个元素被赋值为2，再src++，dst++。
（3） 当src++和dst++后，nums[src]为数组第三个元素的位置，nums[dst]为数组第二个元素的位置。此时nums[src]等于val，所以src++。
（4） 此时nums[src]在后面数组外，超出数组的范围，即可为不满足src小于numsSize的条件，跳出循环，返回dst值。
运行代码：
int removeElement(int* nums, int numsSize, int val)
{int src = 0;int dst = 0;while(src < numsSize){if(nums[src] == val){src++;}else{nums[dst++] = nums[src++];//dst++;//src++;}}//此时dst指向的位置就是要返回的有效个数return dst;
}运行提交结果：
2、删除有序数组中的重复项
删除有序数组中的重复项 - 力扣（LeetCode）
思路分析：
思路一：指针指向第一个元素，然后与它后面的元素进行比较，若相等，第一个元素和它后面的一个元素以外的整体前移；若不相等，则指针后移一位，以此类推。
思路二：定义两个变量，dst为第一个位置，src为第一个位置的下一个位置，判断src和dst位置的数据，因此有以下两者情况：
（1）若相等，src++；
（2）若不相等，dst++，nums[dst]=nums[src],src++。
思路二只有一层循环，时间复杂度为O（n）；空间复杂度为O（1）
我们以思路二的一个例子来入手分析一下：
（1）此时nums[dst]==nums[src]，所以src++，此时src为第三个元素的位置。
（2）此时nums[dst] != nums[src]，则dst++，此时dst为第二个元素的位置，所以使nums[dst]=nums[src]，再让src++。
（3）此时nums[src]在后面数组外，超出数组的范围，即可为不满足src小于numsSize的条件，跳出循环，返回dst值。
总结规律：
两个重复的元素必定相邻，不可能中间有间隔的元素，所以直接相当于把重复的元素删掉，只保留不重复的元素，保持有序性。
运行代码：
int removeDuplicates(int* nums, int numsSize)
{int dst = 0, src = dst+1;while(src < numsSize){//nums[dst] nums[src]//相同（重复） src++//不相同，dst++，赋值，src++if(nums[dst] != nums[src] && ++dst != src){nums[dst] = nums[src];}src++;}return dst+1;
}运行提交结果：
3、 合并两个有序数组
合并两个有序数组 - 力扣（LeetCode）
思路分析：
根据题目要求，我们可以创建三个指针，分别指向num1最后一个有效数据位置，num2最后一个数据位置，和num1最后一个位置，比较了l1和l2位置的数据，谁大，谁就往l3位置放数据，同时往l3放数据的这个指针和l3这个指针往前移动一个位置，另一个指针不动，继续以上操作。
结束条件：以两种情况为主
（1）l1<0：要处理nums2中数据，循环放到num1中。
（2）l2<0：不需要处理，因为nums2中的数据已经有序的放到num1中了。
我们以该思路分析以下例子：
最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
（1）l1和l2的数据相比较，l1的数据大，放到l3的位置处。
（2）同时l1和l3往前移动一个位置 ，l2不动。
（3）以此类推，重复以上操作，直到l1或l2其中之一指向数组之外。
情况一：
此例子是l2指向数组之外，即l2<0，此时表明不需要处理，因为nums2中的数据已经有序的放到num1中了。
情况二：
我们以另一种情况来看，即l1<0，要处理nums2中数据，循环放到num1中，同时往l3放数据的这个指针和l3这个指针往前移动一个位置，另一个指针不动。
该思路只有并列的两层循环，时间复杂度为O（n）或O（m）；空间复杂度为O（1）
运行代码：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int l1 = m - 1;int l2 = n -1;int l3 = m + n - 1;//l1 >= 0 l2 >= 0while(l1 >= 0 && l2 >= 0){if(nums1[l1] > nums2[l2]){nums1[l3--] = nums1[l1--];}else{//l1 == l2 要么 l2 > l1nums1[l3--] = nums2[l2--];}}//跳出while有两种情况：要么l1 < 0（需要处理），要么l2 < 0（不需要处理）while(l2 >= 0){nums1[l3--] = nums2[l2--];}
}运行提交结果：
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
为了利用数组 nums 1与 nums 2已经被排序的性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。
初始两数组状态如下：
排序后的效果：
运行代码：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int p1 = 0, p2 = 0;int sorted[m + n];int cur;while (p1 < m || p2 < n) {if (p1 == m) {cur = nums2[p2++];} else if (p2 == n) {cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {cur = nums1[p1++];} else {cur = nums2[p2++];}sorted[p1 + p2 - 1] = cur;}for (int i = 0; i != m + n; ++i) {nums1[i] = sorted[i];}
}
复杂度分析：
- 时间复杂度：O(m+n)。指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
- 空间复杂度：O(m+n)。需要建立长度为 m+n 的中间数组 sorted。
二、顺序表问题与思考
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容⼀般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200， 我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。