顺序表算法题 —— 移除元素、删除有序数组中的重复项、合并两个有序数组

目录

一、顺序表算法题

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];}
}

复杂度分析：

1. 时间复杂度：O(m+n)。指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
2. 空间复杂度：O(m+n)。需要建立长度为 m+n 的中间数组 sorted。

二、顺序表问题与思考

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容⼀般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200， 我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？这就需要引入链表的相关内容了，请听下回博客详细分解。