【C语言】LeetCode 27. 移除元素 的n种解法
2023-04-18 16:06:27 时间
题目描述
OJ链接:27. 移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解法一 快慢下标
设置初始值为0的快慢下标slow和fast,如果fast位置不是val值,则赋值给slow,下标都增1,那就会保留下值。
如果fast位置是val值,fast自增1,不赋值就不会再被数组保留,一次遍历后,val值就被排掉了。
时间复杂度:O(N)
空间复杂度:O(1)
int removeElement(int* nums, int numsSize, int val){
//定义快慢下标
int slow =0;
int fast =0;
//临时变量储存数组大小
int maxRange=numsSize;
while(fast<maxRange)
{
//如果不等于,fast位置赋值给slow位置,下标都增1
if(nums[fast]!=val)
{
nums[slow]=nums[fast];
++slow;
++fast;
}
else//如果等于,不赋值,fast直接跳过
{
--numsSize;
++fast;
}
}
return numsSize;
}//timeO(N) spaceO(1)
//for循环写法,简练写法
int removeElement(int* nums, int numsSize, int val){
int slow =0;
for(int fast=0;fast<numsSize;fast++)
{
if(nums[fast]!=val)
{
nums[slow]=nums[fast];
++slow;
}
}
return slow;
}
解法二 数组移位
通过将数组整体移位是我们常用的删除数组元素的方法,只是这种方法在删除多个元素时效率并不高。
时间复杂度:O(N*N)
空间复杂度:O(1)
int removeElement(int* nums, int numsSize, int val){
for(int i=0;i<numsSize;++i)
{
if(nums[i]==val)
{
//将后半部分数组整体迁移1
for(int j=i;j<numsSize-1;++j)
{
nums[j]=nums[j+1];
}
--numsSize;
//一定要--i,确保每个元素都被筛选,是否等于val
--i;
}
}
return numsSize;
}//timeO(N*N) spaceO(1)
码字不容易,欢迎关注,点赞,收藏,评论,转发。
相关文章
- 测试效率提升一倍!第二届NCTS中国云测试峰会开启AI测试新范式
- 不会编程也能写程序 - Testin AI 新产品iTestin发布
- 自由开源 Linux 手机 Librem 5 第二批将延期发货
- 苹果软件工程师讲述“安全码自动填充”功能背后的故事
- Google硬件全家桶大更新!槽点简直和亮点一样多
- 报告:华为鸿蒙2020年全球份额将达2% 成第五大操作系统
- 把全国人民拉进一个微信群,技术上能实现吗?
- 微信提醒:这些都是外挂软件 大家不要用
- 谷歌官方首次提及Android 11
- 智能手机如果十年不坏,你能坚持十年不换吗?
- 苹果正式放弃iTunes!如何将iPhone和iPad同步到Mac?
- Android 11 将推出系统试用功能,满意后再正式安装
- Mate 30 Pro正面对决iPhone 11 Pro Max:流畅度完胜
- 苹果历代iPhone能用几年?三个维度详细分析
- 5G元年,华为Mate30开启了怎样的手机进化战争?
- 一文看懂两款顶级芯片——苹果A13打得过麒麟990吗?
- iPhone 11是一次「下沉」还是「归位」?
- 小程序也可以跟踪托运行李,终于能知道你的行李到哪了
- 计算机组成原理:计算机的层次与编程语言
- 为什么「暗色模式」不应采用纯黑背景?这是谷歌的理由