数据结构之顺序表相关算法题

一、移除元素

移除元素 - 力扣

思路一：就是创建一个临时数组，对原数组进行遍历，找出与val不同的数据放到新数组里，然后再将tmp中的数据导回原数组

这个思路的复杂度很好猜，空间复杂度为O（N），时间复杂度为O（N） 但是

int tmp[numsSize];

这里是变长数组，某些编译器上是不支持变成数组的，比如说msvc，这里使用动态内存开辟空间更好

而且该题目说要原地移除，这种方法是使用了一个临时数组，也是不太符合题目的

思路二：双指针法，创建两个变量 dst，src src在前面探路（找非val值） dst在后面站岗（保存非val值）

1. 如果src指向的数据是val，src++
2. 如果src指向的数据不是val，赋值（src指向的值给dst），src和dst都++

在这里插入图片描述

在这里插入图片描述

结果只保证前dst个数据为2，剩下的不管

在这里插入图片描述

二、删除有序数组中的重复项

删除有序数组中的重复项 - 力扣

在这里插入图片描述

在这里插入图片描述

思路1：创建新数组，遍历原数组，将不重复数据导入新数组中，再将新数组中的数据导入到原数组中

在这里插入图片描述

因为涉及不重复数据的导入，所以要定义两个变量来遍历，初始化i=j，第一个数据直接拿，接下来j++，此时i==j，i和j整体++，接下来i和j不相等，不相等把j向新数组中放，之后i与j再++

在这里插入图片描述

此时j越界，将新数组数据导入原数组中

在这里插入图片描述

前两个数据是唯一的数据，满足题目要求 该思路的唯一一个小问题也是没有在原数组的基础上进行操作，且很好猜时间和空间复杂度为O（n）

于是就有了思路2： 依旧是使用双指针法：创建两个变量，分别指向数组起始和下一个位置

1. 如果src的值和dst的值相等，src++
2. 如果src的值和dst的值不相等，dst++，赋值，src++

在这里插入图片描述

最后src越界，当前数组里的值2，3，3，3，前两个数据是2，3，满足题意

在这里插入图片描述

dst指向下标为1的数据，此时返回dst+1

在这里插入图片描述

示例二按该思路推导结果如下，也是满足的，前5个数据是唯一的数据

代码如图

在这里插入图片描述

优化1

在这里插入图片描述

如图刚开始src！=dst，dst++再src给dst赋值，此时的赋值就非常多余 所以有了如下代码：

在这里插入图片描述

由于两个if嵌套是且的关系，所以还可以优化

在这里插入图片描述

三、合并两个有序数组

合并两个有序数组 - 力扣

在这里插入图片描述

在这里插入图片描述

思路1： 先合并数组，再对nums1进行排序，可以使用冒泡排序，不过时间复杂度较高，为O（N2）

思路2：类似于尾插操作，从后往前遍历数组，找大（谁大谁先往后放） 这里定义l1，l3为nums1的下标，l1放到有效数据的最后一个位置。l3指向m+n-1这个位置，是用来存放数据的位置，l2为nums2的下标，指向n-1的位置

在这里插入图片描述

首先l1与l2比较，因为6大，所以6存放到l3的位置，之后l2，l3减减

在这里插入图片描述

此时l1与l2比较，l2大，5放到l3位置，放完之后l2，l3再减减

在这里插入图片描述

同样推理操作后，l1大，l1，l3减减

在这里插入图片描述

此时l1，l2均为2，假设l2的数字大，将2放到l3的位置

在这里插入图片描述

此时l2，l3再减减，此时l2越界，nums1已有序，且nums2先越界，也有相反的情况

在这里插入图片描述

同样的思路，l1与l2相比，6放l3的位置，此时l1与l3减减

在这里插入图片描述

l1与l2再比较，5大放l3，l1与l3减减

在这里插入图片描述

同样思路，如图步骤之后l2，l3减减

在这里插入图片描述

此时假设l1大，放到l3的位置

在这里插入图片描述

之后l1，l3减减，此时l1已经越界，跳出循环，此时nums2中还有两个数据没有放到第一个数组中，此时只需将剩下两个数据循环放到nums1中即可

在这里插入图片描述

此时也是有序的

代码如下：

总结

以上就是数据结构顺序表相关算法题的内容了，这些算法题的代码普遍很简答，主要就是在思考上。喜欢的靓仔靓女们不要忘记一键三连给予支持哦~