写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【原地操作】【双指针】【数组】
题目来源
面试经典 150 题 —— 27. 移除元素
题目解读
移除数组 nums
中的 val
值,要求原地操作,但是数组中的元素顺序可以改变,最后输出移除所有 val
后数组的长度。
解题思路
方法一:原地操作
原地操作,那么我们就不能使用额外的数组来存放非 val
的元素从而实现移除操作,但是我们可以使用 “覆盖” 的思想来模拟移除操作。
具体地,维护两个指针 i
和 j
,i
指针用来遍历数组查找哪个位置上的元素等于 val
,j
指向用来覆盖 i
位置的元素。初始化 i = 0
、j = nums.size() - 1
,只要 nums[i] = val
,我们就用 nums[j]
来覆盖,使用了 nums[j]
之后,j
指针就要左移指向下一个将要使用的元素;只有 nums[i] != val
时,我们才会右移 i
指针,准备处理下一个元素。
直到 i
指针超过 j
指针,表明可以被用来覆盖的元素已经没有了,i
的值就是原数组中的非 val
的数,直接返回 i
。
实现代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0, j = nums.size() - 1;
while (i <= j) {
if (nums[i] == val) {
nums[i] = nums[j--];
}
else ++i;
}
return i;
}
};
复杂度分析
时间复杂度:
O
(
n
)
O(n)
O(n),
n
n
n 为原数组 nums
的长度。
空间复杂度: O ( 1 ) O(1) O(1),仅使用了两个指针变量,是原地操作。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。文章来源:https://www.toymoban.com/news/detail-706371.html
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。文章来源地址https://www.toymoban.com/news/detail-706371.html
到了这里,关于【面试经典150 | 数组】移除元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!