【初阶数据结构与算法】沉浸式刷题之顺序表练习(顺序表以及双指针两种方法)

顺序表练习

   在顺序表练习中我们会首先使用我们学过的顺序表来解决，然后再同时介绍一下其它方法，在练习开始之前我们要说明一个东西，就是我们之前不是写好了一个顺序表吗？我们等一下就直接全部复制过来用
   那么是不是就说明我们以后要用数据结构做题就必须把它手写一遍吗？这是不需要的，后面我们会介绍C++，在C++中的STL中有现成的可以用，现在我们还没有介绍到，就复制我们写过的数据结构来做题
   在做题过程中，我们也会计算这些方法的时间复杂度和空间复杂度，也是对之前内容的一个复习

1.移除数组中指定的元素

题目链接：https://leetcode.cn/problems/remove-element/description/

方法1（顺序表）

   我们先来看看题目描述：

   题目中的第一个用例：

   题目给出的函数模型：

   根据上面的图片描述，我们基本明确了题意，就是给我们一个数组和一个值，然后把数组中和这个值相等的元素移除掉，最后返回处理后的数组中的有效元素个数
   方法1的思路就是直接使用我们的顺序表，在顺序表中我们提供了查找方法，并且提供了删除指定位置元素的方法，我们就可以在顺序表中查找要删除的元素，然后把返回来的下标作为参数传给删除函数
   首先我们把写过的顺序表拷贝到题目中，在使用顺序表之前，我们要创建一个顺序表，并且使用初始化方法对它初始化，为了防止忘记销毁顺序表，我们可以先把顺序表的销毁也一起配套写上
   随后把数组中的内容尾插到我们的顺序表，我们才能使用顺序表对数据进行操作，如下：

int removeElement(int* nums, int numsSize, int val) 
{int i = 0;SL sl;SLInit(&sl);for(i = 0; i<numsSize; i++){SLPushBack(&sl,nums[i]);}SLDestroy(&sl);
}

   随后我们就设计一个循环，让它能够一直找题目给出的元素，然后每找到一个就调用删除方法把它删除，那么循环的结束条件是什么呢？我们可以根据查找方法的返回值来设计，如果没有在顺序表中找到对应的元素会返回-1
   那么我们就判断它的返回值是否是-1，如果不是就进入循环将对应的元素删除，是的话就结束循环，如下：

while(SLFind(&sl,val) != -1)
{int ret = SLFind(&sl,val)SLErase(&sl,ret);
}

   处理完毕之后我们就把顺序表中的内容重新放入原数组，并且将数组有效元素个数记录下来，完整代码如下：

int removeElement(int* nums, int numsSize, int val) 
{int i = 0;SL sl;SLInit(&sl);for(i = 0; i<numsSize; i++){SLPushBack(&sl,nums[i]);}while(SLFind(&sl,val) != -1){int ret = SLFind(&sl,val);SLErase(&sl,ret);}for(i = 0; i<sl.size; i++){nums[i] = sl.arr[i];}int k = sl.size;SLDestroy(&sl);return k;
}

   我们看看提交的结果：

   可以看到最后通过了，我们来分析一下代码的时间复杂度和空间复杂度，第一个和第二个for循环都是O(N)，关键在于第二个while循环的时间复杂度
   由于我们的查找方法和删除方法时间复杂度都是O(N)，外层有一个while循环，所以时间复杂度就是O(N^2)，不是很好的一个时间
   接着来看空间复杂度，我们为了在顺序表中操作数组的数据，所以把数组中的数组全部放入了顺序表，所以顺序表会额外开辟数组元素大小的空间，空间复杂度为O(N)
   我们知道这个时间复杂度和空间复杂度都不是很好，所以我们要接着介绍另一个方法

方法2（双指针）

   这里的双指针不是创建两个指针变量，而是指数组中的下标，因为在数组中我们能够通过下标找到对应的元素，与指针很像，所以叫双指针
   具体方法就是创建两个整型变量src和dest，这两个名字在我们指针章节出现得不少，src代表源，dest代表目的地
   在双指针算法中，我们的思路很简单，就是首先让src和dest都指向数组的第一个元素，随后我们就看src位置上的值是否是题目给出的val，如果是我们就直接让src往后走一步
   如果不是，我们就把src位置上的值赋给dest，随后让dest和src都往后走一步，接下来我们就演示一下第一个示例的推演，如图：



   有了上图的分析，我们就可以来实现一下代码了，首先创建两个整型变量src和dest作为我们的双指针，初始情况下让它们都为0
   随后创建一个循环，循环条件就是src<numsSize，因为src是数组中的下标，要保证它不能越界，接着我们就进行判断，如果src位置的值等于dest位置的值，那么直接让src++
   否则的话就是不等于，那么把src位置的值赋值到dest位置，随后让它们都++，如下：

while (src < numsSize)
{if (nums[src] == val){src++;}else{nums[dest++] = nums[src++];}
}

   最后我们直接返回dest即可，完整代码如下：

int removeElement(int* nums, int numsSize, int val) 
{int src = 0;int dest = 0;while(src < numsSize){if(nums[src] == val){src++;}else{nums[dest++] = nums[src++];}}return dest;
}

   最后我们提交一下就通过了，在双指针方法中，我们只有一个循环，时间复杂度为O(N)，申请的空间也是常数个，所以时间复杂度为O(1)，可以看到比使用顺序表的方法简便多了，时间复杂度和空间复杂度都降低了一个档次
   这道题的双指针法的本质就是，碰到了指定的元素就不管，直接跳过，然后把不是指定的元素放在前面，简单地说就是一个在前面探路，一个在后面接收

2.删除有序数组中的重复项

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

方法1（顺序表）

   在这个题目中，方法1我们还是使用顺序表来做，我们首先来看看题目描述：

题目的第一个示例：

题目给出的函数原型：

   根据上面图片的解释，我们大致明白了题目的要求，就是数组是相对有序的，然后我们要删除那些重复项，让数组里面的元素变得唯一，最后返回唯一的元素个数，至于其它位置的元素就不管了
   首先我们还是拷贝顺序表代码，以及创建、销毁顺序表，把数组中的数据尾插到顺序表中，上面讲过了，接着我们就来讲这道题不同的地方
   由于数组是相对有序的，所以相同的元素肯定是放在一起的，所以我们就可以写一个循环来判断前后两个元素是否相等，如果相等我们就删除当前的元素，每删除一个元素numsSize就减1，要特别注意的一个点是要保证下标的有效性，如下：

for (i = 0; i < numsSize; i++)
{if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1]){SLErase(&sl, i);numsSize--;}
}

   但是如果我们去运行这段代码就会发现第二个示例会出错，如下：

[0,0,1,1,1,2,2,3,3,4]

   我们把这个示例放到VS中调试一下，如图：

   这个时候我们发现了问题，当i = 1时，将下标为1的元素删除了，所有后面的其它元素都往前挪动了一步，导致现在下标为1和2的元素又相等了
   但是本次循环结束了，下一次在循环中i要++变成了2，i+1变成了3，比较不了下标为1和2的元素了，也就导致了下标为1和2的元素相等没有处理，如果看不懂这里的分析也没有关系，自行调试一下就明白了
   那么怎么解决呢？其实也很简单，问题就出在删除一个相同元素后，其余元素都往前挪动了，但是循环结束了，i要++，就不会再比较移动后的i下标位置的元素和i+1下标的元素了
   所以我们为了能够让它删除元素后，多比较一次原本移动后的i下标位置的元素和i+1下标的元素，我们可以在删除一个元素后让i- -，这样处理后下次进入循环i的值就不会变化，代码如下：

for (i = 0; i < numsSize; i++)
{if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1]){SLErase(&sl, i);numsSize--;i--;}
}

   当完成上面的步骤之后我们再把顺序表中的数据拷贝回原数组中，此时的numsSize就是有效的元素个数，完整代码如下：

int removeDuplicates(int* nums, int numsSize)
{SL sl;int i = 0;SLInit(&sl);for (i = 0; i < numsSize; i++){SLPushBack(&sl, nums[i]);}for (i = 0; i < numsSize; i++){if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1]){SLErase(&sl, i);numsSize--;i--;}}for (i = 0; i < numsSize; i++){nums[i] = sl.arr[i];}SLDestroy(&sl);return numsSize;
}

   最后我们提交一下就可以通过了，在这个方法中，我们的时间复杂度也是很高的，达到了O(N^2)，并且由于使用顺序表拷贝了原数组中的内容，空间复杂度也不低，达到了O(N)，所以我们接下来介绍一个更好的方法

方法2（双指针）

   这道题还是可以使用我们的双指针法来做，上一题的双指针法的本质就是，碰到了指定的元素就不管，直接跳过，然后把不是指定的元素放在前面，本质就是一个在前面探路，一个在后面接收
   这道题也可以借鉴这样的思想，我们题目要求去掉相对有序的数组中的元素，说明相等的元素都是挨在一起的，我们还是可以定义两个变量src和dest，src在前面探路，dest在后面接收
   具体思路就是：初始情况下让dest指向第一个元素，而src指向第二个元素，因为如果它们都指向第一个元素，那么它们肯定就相等了，没有比较的必要，所以让src走到第二个元素的位置上
   然后我们就比较src和dest位置上的元素是否相等，如果相等我们就让让src++，其它什么都不做，如果不相等就让dest++，然后把src位置的值赋值到dest位置上，然后再让src++，听着可能有点懵，我们来画个图理解一下，就知道这个思路了
   具体的例子我们就参考题目给出的第一个示例，如下：


   有了上图的解析，我们现在就可以直接来写代码了，首先创建一个while循环，条件就是src<numsSize，因为src是数组的下标，不能越界
   然后如果src指向的元素等于dest指向的元素，就让src++，其它什么都不做，如果不相等，就让dest先++，再把src位置的元素赋值给dest位置的元素，最后让src++，如下：

while (src < numsSize)
{if (nums[src] == nums[dest]){src++;}else{dest++;nums[dest] = nums[src];src++;}
}

   写出来之后我们可以对它进行一下优化，让代码不那么臃肿，如下：

while (src < numsSize)
{if (nums[src] == nums[dest])src++;elsenums[++dest] = nums[src++];
}

   最后循环结束后我们再返回dest+1即可，完整代码如下：

int removeDuplicates(int* nums, int numsSize) 
{int src = 0, dest = 0;while(src < numsSize){if(nums[src] == nums[dest])src++;elsenums[++dest] = nums[src++];}return dest+1;    
}

   最后就可以成功提交代码了，我们再来分析一下双指针法的时间复杂度和空间复杂度，我们只使用了一个循环，时间复杂度为O(N)，只申请了有限个大小的空间，所以空间复杂度为O(1)，相较于上一个方法优化了许多

3.双指针练习之合并两个有序数组

题目链接：https://leetcode.cn/problems/merge-sorted-array/description/

方法1（直接排序）

   虽然这道题我们是用来练习双指针的，但是我们还是有必要知道一下这道题的其它解决办法，并且这个解决方法还不难，所以放在这里简单说一下
   我们先来看看题目描述：

   题目第一个示例：

   题目给出的函数原型：

   题目的大致含义就是，给了我们两个数组，其中第一个数组nums1的大小是两个数组有效元素个数的和，因为我们后面要把nums2数组中的元素放到nums1中去，所以要保证nums1数组的大小足够
   首先题目还是告诉我们这两个数组是非递减的数组，也就是递增的数组，只是有可能有重复的数据，现在就要求我们将这两个有序的数组合并，并且保持合并后还是有序的
   第一个方法很简单，不是保持合并后还是有序吗，直接把nums2数组的数据先插入num1数组，然后对整个nums1数组进行排序，排序我们可以选择qsort函数，没有学过qsort函数的友友可以参考文章：【C语言】手把手带你拿捏指针(4)（含qsort函数详解）
   也可以选择我们之前学过的冒泡排序，但是其实冒泡排序的效率是比较低的，后面我们会把所有常见的排序算法都讲一下，比如快排，堆排等等，qsort函数的底层就是使用的快排实现
   代码的实现过程就不再多讲了，思路很简单，这里我们直接给出完整代码：

#include <stdlib.h>int int_cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{ for(int i = 0; i<n; i++){ nums1[i+m] = nums2[i]; }  qsort(nums1, m+n, sizeof(int), int_cmp);
}

   可以看到代码的逻辑是很简单的，并且效率是很快的，因为qsort底层使用的是快排，时间复杂度仅仅为O(N * logN)，空间复杂度也是O(1)，那么还有没有更快的方法呢？当然有，就是我们马上介绍的双指针法

方法2（双指针）

   其实我们今天练习的三道题其实都很类似，所以都可以使用双指针来做，只是在这道题中我们有两个数组需要合并，我们还是可以试着用之前的思路来思考一下这道题，只是之前是一个数组，只需要一个src，这道题我们可以定义两个指针src1和src2
   之前的两个题思路就是，如果碰到相等的元素或者题目给出的元素，就把它跳过，使用后面的元素将它覆盖，而这道题我们该怎样做呢？
   首先就是第一个思路，我们定义src1指向nums1数组的第一个元素，src2指向nums2数组的第二个元素，然后由于要把最后的结果保存到nums1中，所以dest就指向nums1中的第一个元素
   随后我们比较src1指向的元素和src2指向的元素哪个小，哪个小就把它放到dest的位置上，然后让dest++，然后src1++或者src2++，最后循环这个步骤
   但是我们最后发现这个思路有点问题，问题出在nums1数组中，因为如果我们直接把数据放在dest，也就是从nums1数组的开头开始存放数据，会导致原本的nums1数组的数据被覆盖，我们举个例子，如图：

   此时我们就发现问题了，nums1中的数据会被覆盖，所以第一种思路并不可行，那么怎么避免数据被覆盖呢？这个时候我们就可以从nums1数组的最后面开始操作数据，也就是让我们的dest默认指向nums1数组的最后一个位置
   因为我们要保证nums1最后排序成相对递增，最后一个位置就要放最大的值，怎么办呢？我们可以让src1和src2分别指向nums1和nums2数组中有效元素的最后一个元素，然后它们两个指向的元素谁大就让它放入dest的位置
   然后让dest- -，以及src1- -或者src2- -，就这样一直从后往前找大放入dest位置，循环条件就是要让src1和src2都要大于等于0，因为它们是数组的下标，不能越界，最后就可以使得数组是相对递增的，这就是我们的第二个思路，接下来我们就用第一个示例来画个图理解一下：



   可以看到我们这里将两个数组合并到了nums1中，让数组nums1有序了，但是其实有一个问题，如果我们最后时src2先越界，那么说明nums2数组中的数据已经全部放入nums1了，循环结束了，剩下的nums1的数据也已经保持了有序，所以src2首先越界代码没有问题
   但是有可能下一次src1首先越界，说明nums1中原本的有效的元素已经放在nums1数组后面了，循环结束了，但是nums2数组还没有放完呀，这个时候就会出错，所以我们还需要在这个循环结束后用一个新的循环判断一下
   如果src2还大于等于0，说明nums2数组中的内容还没有全部移动到nums1中，此时我们只需要循环地让数组nums2中的元素移动到nums1的dest位置，接下来我们的代码才能完全没问题，如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{int src1 = m-1;int src2 = n-1;int dest = m+n-1;while(src1>=0 && src2>=0){if(nums1[src1] > nums2[src2]){nums1[dest--] = nums1[src1--];}else{nums1[dest--] = nums2[src2--];}}while(src2 >=0){nums1[dest--] = nums2[src2--];}
}

   接着我们提交一下：

   可以看到代码成功通过了，我们再来分析一下这个代码的时间复杂度和空间复杂度，可以发现我们虽然有两个循环，但是实际上深入计算会发现两个循环的次数加起来为O(N)，所以时间复杂度是标准的O(N)
   并且由于申请的是有限个空间，所以空间复杂度是O(1)，我们就可以看出来了，虽然我们的快排很快，时间复杂度仅为O(N * logN)，但是我们的双指针更快，只有O(N)

   那么今天的分享就到这里结束啦，我们今天使用了顺序表来做了两道题，用一个题来专门学习双指针算法，但是这三道题都使用了我们的双指针算法来解决，以后类似的题就可以使用双指针，效率是很高的
   不知道友友们有没有收获什么新知识呢，欢迎在评论区留言，有问题欢迎直接私信我
   那么今天就撤啦，bye~