给定一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度?
数组 一个 需要 元素 所有 返回 长度 数值
2023-09-14 09:14:07 时间
例题:给定一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度。例如:nums={0,1,2,2,3,0,4,2},val=2;输出: 5 nums={0,1,3,0,4}顺序任意。
目录
方法一:暴力求解法
所谓暴力求解法,就是遍历整个数组,去找与val相同的值,找到以后,就以此时的下标为条件;再写一层循环,让后面的元素依次往前移,每次移动都会有元素覆盖,让元素个数n--;最后根据元素的个数进行打印即可。
时间复杂度为O(
),空间复杂度为O(1)
具体代码如下:
代码分析:
这个代码很好理解;在这里我只提示一点就是i--回朔的过程,下面通过画图来理解一下:
方法二:双指针法(快慢指针)
这种方法我也是刚接触,很玄妙;就是开始定义两个变量src、dest;让arr[src]和arr[dest]都指向同一位置;
当arr[src] != val;我们让arr[src]的值覆盖arr[dest],即arr[dest] = arr[src],并且让src++、dest++;
当arr[src] == val时,只让src++;直到下一次arr[src] != val;重复上面的操作!!!其实也就是覆盖,和第一种方法很相似,处理方式不同而已。
时间复杂度为O(N),空间复杂度为O(1)
下面看具体代码:
代码分析:
如果你还不理解这种思想,不妨我们通过画图的形式去解释:
这里dest的下标是5,其实就是前面元素的个数,是不是很巧妙;所以这种双指针法我们一定要掌握;如果自己理解不了,不妨自己动手画画吧!!!
相关文章
- numpy 数组拼接方法
- shell脚本之awk数组
- java json数组转json对象_json对象数组
- 2022-10-19:一个数组如果满足 : 升降升降升降... 或者 降升降升...都是满足的 给定一个数组, 1,看有几种方法能够剔除一个元素,达成上述的要求
- json数组转对象集合_解析json字符串转成对象集合
- ES6常用数组方法总结(max,contant,some,every,filter,reduce,forEach,map)
- 2022-12-16:给你一个长度为n的数组,并询问q次每次询问区间[l,r]之间是否存在小于等于k个数的和大于等于x每条查询返
- 2022-12-22:给定一个数字n,代表数组的长度,给定一个数字m,代表数组每个位置都可以在1~m之间选择数字,所有长度为n的
- 2023-01-12:一个n*n的二维数组中,只有0和1两种值,当你决定在某个位置操作一次,那么该位置的行和列整体都会变成1,不
- 2023-01-14:给定一个二维数组map,代表一个餐厅,其中只有0、1两种值map[i][j] == 0 表示(i,j)位置
- 2023-03-16:给定一个由 0 和 1 组成的数组 arr ,将数组分成 3 个非空的部分, 使得所有这些部分表示相同的二进制值。 如果可以做到,请返回任
- 2023-03-28:有一根长度为 n 个单位的木棍,棍上从 0 到 n 标记了若干位置。 给你一个整数数组 cuts ,其中 cuts[i] 表示你需要将棍子
- 2023-04-13:给定一个字符串数组strs,其中每个字符串都是小写字母组成的, 如果i < j,并且strs[i]和strs[j]所有的字符随意去排列能组
- 2023-04-20:有一堆石头,用整数数组 stones 表示 其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出任意两块石头,然后将它
- PHP file():把整个文件读入一个数组中
- 打印给定数组中元素和为0的所有子数组详解编程语言
- C++用类模板实现可变长数组
- java解一个比较特殊的数组合并题
- javascript数组与php数组的地址传递及值传递用法实例