这一系列的博客主要是讲解一些比较经典的，笔试常见的数据结构题目，由于我也是刚刚开始学习数据结构，所以更新的内容肯定是偏简单的，难度会跟着学习的深入而上升。
27. 移除元素OJ链接题目介绍：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/remove-element具体信息可以打开链接查看。本题我们提供三种方法：方法1. 暴力求解大致思路是：遍历数组，找到需要移除的元素再进行移除。时间复杂度：O(n^2)空间复杂度：O(1)图解思路：完成过后需要注意两点：i需要继续待在当前的位置，而for循环会导致i++，所以我们需要手动进行i--删除了数组中的一个元素后，数组大小变小，需要进行numsSize--代码如下：int removeElement(int* nums, int numsSize, int val)
{
//遍历数组
for(int i=0;i<numsSize;i++)
{
if(nums[i]==val)
{
//如果找到了val，从i开始，将数组左移一格
for(int j=i;j<numsSize-1;j++)
{
nums[j]=nums[j+1];
}
//移动完毕后，i--保证下一次还是从i开始遍历，numsSize--表示数组总元素减1
i--;
numsSize--;
}
}
return numsSize;
}
代码提交结果：方法1总结方法1的思想很简单，但是时间复杂度很高，虽然能够完成任务，但是算法并不好。方法2. 以空间换时间大致思路是：重新创建一个新数组，将原数组中不是val的值放入新数组中。再将新数组的内容拷贝回原数组。时间复杂度O(n)空间复杂度O(n)图解思路：代码如下：int removeElement(int* nums, int numsSize, int val)
{
//动态开辟内存，即开辟一个容量为numSize的新数组
int* tmp=(int*)malloc(sizeof(int)*numsSize);
int src=0,dst=0;
while(src<numsSize)
{
//将原数组中不为val的元素拷贝至新数组中
if(nums[src]!=val)
{
tmp[dst]=nums[src];
src++;
dst++;
}
else
{
src++;
}
}
memcpy(nums,tmp,sizeof(int)*dst);
free(tmp);
//这里新数组的大小其实就是dst可以画图理解一下
return dst;
}
运行结果：方法2总结以空间换时间的思想在数据结构中会经常遇到，希望大家能够熟悉。方法3. 方法2的优化方法2已经是很好的算法了，但是我们能不能再优化呢？也就是说我们能不能试着创建一个新数组，直接在原数组中进行操作。时间复杂度O(n)空间复杂度O(1)图解：完成后数组结构如下：有效元素个数为j+1代码如下：int removeElement(int* nums, int numsSize, int val)
{
int src = 0, dst = 0;
int count = 0;
while (src <= numsSize - 1)
{
//src不等于val就拷贝并记录拷贝的数据个数
if (nums[src] == val)
{
src++;
count++;
}
else
{
nums[dst] = nums[src];
src++;
dst++;
}
}
return numsSize - count;//这里写成dst+1也可以
}
运行结果：26. 删除有序数组中的重复项本题其实和上一题差不多。提供一种比较好的解法，思路与上一题的方法3相似。思路：双指针src和dst，最开始同时指向第一个元素，元素相同则src++，否则dst++并且将src指向的内容拷贝至dst中，src++，最后的数组有效元素个数为dst+1。图解：代码如下：int removeDuplicates(int* nums, int numsSize)
{
int src=0,dst=0;
while(src<numsSize)
{
//相同则跳过，否则就拷贝
if(nums[src]==nums[dst])
{
src++;
}
else
{
dst++;
nums[dst]=nums[src];
src++;
}
}
return dst+1;
}
运行结果：}