数据结构十一：数组相关经典面试题

本篇博客详细介绍分析数组/顺序表常见的面试题，对于前面所学知识进行一个巩固，同时介绍一些力扣刷题中的一些概念：如：输出型参数等，在刷题中培养自己的编程思维，掌握常见的编程套路，形成题感！

第一题：移除元素

1.1 题目描述

1.2 解题分析

本题另加要求：时间复杂度为O(n), 如果单纯利用顺序表删除元素的思想：只要遇到待删除指定元素，则从该元素位置开始，从前依次向后挪动数据进行元素覆盖，从而达到删除元素的效果，但是这样如果数组长度较大且该值出现次数非常多，那么，它的时间复杂度为：O(n^2)不符合要求，因此，这种思路时间复杂度不符合要求，换种思路：如果没有空间复杂度要求，我们可以这么做，先申请一块同样大小的数组，将原数组从前向后遍历，不等于待删除元素的，将其放到新数组，等于待删除元素的留在原地不要动，最后再将新数组元素遍历依次赋值给原数组，便可以达到要求，但是，这样空间复杂度不符合要求！！O(n)

经过上面的分析，我们如果不申请数组，直接在原数组上直接进行覆盖，那是不是就可以达到要求？答案是肯定的！这便要引入：双指针思想。

1.3 实现过程

借助双指针思想，时间复杂度O(n),空间复杂度：O(1) 思路如下：

step1. 定义两个整型变量，用作数组的指针，同时赋值为0
step2. 让一个指针src从前向后遍历原数组，如果当前位置是待删除元素，该指针src直接向后走，如果当前位置不是待删除元素，则将该位置元素赋值为另一个指针dst指向的位置，同时这两个指针同时向后走一步；
step3. 直到原数组遍历结束，此时dst所指的位置就是当前数组的有效元素个数，也就是数组的长度，直接返回。

上述这种思想，就可以达到把原数组等于待删除元素的值全部覆盖，从而达到删除的效果！

1.4代码实现

int removeElement(int* nums, int numsSize, int val) 
{//1.定义两个指针int src =0,dst=0;//2.从头开始遍历数组while(src<numsSize){  //3.当前元素不是待删除元素，赋值给dst下标，src、dst继续往后走if(nums[src]!=val){nums[dst]=nums[src];dst++;src++;}//4. 当前元素是待删除元素，不要动，src直接往后遍历，等待不是待删除元素进行覆盖else{src++;}}return dst;
}

第二题：删除有序数组中的重复项

2.1 题目描述

2.2 解题分析

本题与上题有异曲同工之处，同样是删除元素，但是这道题实质上是去重复元素，只保留其中的一个，并且也是要求在原数组基础上进行删除，因此也是借助双指针思想，找到不相同元素，然后进行元素覆盖。

2.3 实现过程

借助双指针思想，时间复杂度O(n),空间复杂度：O(1) 思路如下：

step1. 定义三个整型变量prev、cur、dst,用作数组的指针，其中prev和cur用来比较相邻的两个元素是否相同，dst用来进行元素覆盖。
step2. 如果相邻的两个元素相同，直接让指针prev和cur向后走，dst不要动，如果相邻的两个元素不相同，只会是两种情况：第一种它是一连串相同数字的最后一个，第二种它是一个单独出现的数字（如上面实例2所示），对于第一种情况，很好处理，直接将prev所处位置的元素赋值给dst下标的位置，然后三个指针同时向后走，对于第二种情况，需要最后单独赋值一次，因为：此时cur已经越界，循环无法进入，最后一个单独出现的数字并没有赋值给dst位置，需要单独处理！！！
step3.直到原数组遍历结束，注意：遍历的结束条件为：cur<numsSize，不能用prev,因为cur此时已经越界，无法再继续往后比较了。此时dst所指的位置就是当前数组的有效元素个数，也就是数组的长度，直接返回。

上述这种思想，就可以达到把原数组等于待删除元素的值全部覆盖，从而达到删除的效果！

2.4代码实现

int removeDuplicates(int* nums, int numsSize) {//判空，空数组无法删除if(numsSize==0)return 0;int prev=0,cur=1,dst=0;while(cur<numsSize){if(nums[prev]==nums[cur]){prev++;cur++;}else{nums[dst]=nums[prev];prev++;cur++;dst++;}}nums[dst]=nums[prev];prev++;dst++;return dst;
}