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

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

第一题：移除元素

1.1 题目描述

 

1.2 解题分析

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

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

1.3 实现过程

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

1. step1. 定义两个整型变量，用作数组的指针，同时赋值为0
2. step2. 让一个指针src从前向后遍历原数组，如果当前位置是待删除元素，该指针src直接向后走，如果当前位置不是待删除元素，则将该位置元素赋值为另一个指针dst指向的位置，同时这两个指针同时向后走一步；
3. 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) 思路如下：

1. step1. 定义三个整型变量prev、cur、dst,用作数组的指针，其中prev和cur用来比较相邻的两个元素是否相同，dst用来进行元素覆盖。
2. step2. 如果相邻的两个元素相同，直接让指针prev和cur向后走，dst不要动，如果相邻的两个元素不相同，只会是两种情况：第一种它是一连串相同数字的最后一个，第二种它是一个单独出现的数字（如上面实例2所示），对于第一种情况，很好处理，直接将prev所处位置的元素赋值给dst下标的位置，然后三个指针同时向后走，对于第二种情况，需要最后单独赋值一次，因为：此时cur已经越界，循环无法进入，最后一个单独出现的数字并没有赋值给dst位置，需要单独处理！！！
3. 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;
}

这道题注意边界条件的处理，以及特殊情况的处理，本质思想同第一题。 

第三题：合并两个有序数组

3.1 题目描述

3.2 解题分析

3.3 实现过程

3.4代码实现

第四题：旋转数组

4.1 题目描述

4.2 解题分析

4.3 实现过程

4.4代码实现