LeetCode 27.移除元素

文章目录

• 💡题目分析
• 💡解题思路
• • 🚩思路1:暴力求解 — 遍历
  • 🔔接口源码：
  • 🚩思路2:空间换时间
  • 🔔接口源码：
  • 🚩思路3:双指针（快慢指针）
  • 🔔接口源码：

题目链接👉LeetCode 27.移除元素👈

💡题目分析

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

💡解题思路

🚩思路1:暴力求解 — 遍历

直接一个循环遍历nums数组每个元素；
再对每个元素判断是否和val相等；
相等就把后面的元素往前挪动覆盖它，已达到删除val的目的；
🚨注意：移除元素后，要对数组元素个数 -1，numsSize-1的同时，还要对第一层的for循环遍历的 i 做 i- –,因为元素移动覆盖时候位置发生变化

👇图解👇

🔔接口源码：

int removeElement(int* nums, int numsSize, int val)
{
    int tmp = numsSize ; //创建临时变量,返回时候要用
	int count = 0; //统计移除元素的个数
	for(int i = 0; i<numsSize; i++)
	{		
		if(val == nums[i])
		{
			count++;
			for(int j = i; j<numsSize -1; j++)
			{
				nums[j] = nums[j+1];				
			}
            numsSize--;
            i--; //由于元素都是往前挪动了，所以i也要--
		}
	}
	return tmp - count;
}

此方法：
时间复杂度：O(N^2)
空间复杂度：O(1)

🚩思路2:空间换时间

创建一个新数组 tmp，大小为 numsSize;
同时把原数组 nums中,不等于 val的数据，放到新数组 tmp中；
然后再把 tmp中的数据拷贝回到原数组 nums中；

👇图解👇

🔔接口源码：

int removeElement(int* nums, int numsSize, int val)
{
    int *tmp = (int*)malloc(sizeof(int) * numsSize);
    int j = 0;//执行临时数组的下标
    
    //找不等于val的值放到临时数组
    for(int i = 0; i<numsSize; i++){
        if(val != nums[i]){
            tmp[j++] = nums[i];
        }
    }
    //把临时数组的值，覆盖回去
    //上面的循环结束后，j  = 不是val元素的个数
    for(int i = 0; i<j; i++){
        nums[i] = tmp[i];
    }
    return j;
}

此方法：
时间复杂度：O(N)
空间复杂度：O(N)

🚩思路3:双指针（快慢指针）

定义两个指针：一个dst，一个src;
dst表示目的地指针，src是原指针，src用来移动寻找不等于val的值；
src找到不等于val的值那么就把它赋值给dst对应的值，即 nums[dst] = nums[src],同时dst++; src++；
src碰到与val相等的值，那么src++，其他不变

👇图解👇

🔔接口源码：

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

同理的 ，也可以这样写👇

int removeElement(int* nums, int numsSize, int val)
{
    int dst = 0;
    for (int src = 0; src < numsSize; src++)
    {
        if (nums[src] != val)
        {
            nums[dst] = nums[src];
            dst++;
        }
    }
    return dst;
}

此方法：
时间复杂度：O(N)
空间复杂度：O(1)

🥰希望大家能够理解！

总结🥰
以上就是本题讲解的全部内容啦🥳🥳🥳🥳
本文章所在【C语言刷题】专栏，感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远，也很暗，但是不要怕，不怕的人面前才有路。💕💕💕
小的会继续学习，继续努力带来更好的作品😊😊😊
创作写文不易，还多请各位大佬uu们多多支持哦🥰🥰🥰