-
思路:与 26 题的解法十分相似
- 设置两个指针 \(fast\) 和 \(slow\),其中 \(slow\) 是慢指针,\(fast\) 是快指针
- 当 \(nums[fast]\) 与给定的值相等时,递增 \(fast\) 以跳过该元素
- 当 \(nums[fast] \neq val\) ,交换 \(nums[fast]\) 和 \(nums[slow]\) ,并同时递增两个索引
- 重复这一过程,直到 \(fast\) 到达数组的末尾,数组的新长度为 \(slow\)
-
Code
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.size(); ++fast) {
if (nums[fast] != val) {
swap(nums[fast], nums[slow++]);
}
}
return slow;
}
};
- 复杂度分析
- 时间复杂度:\(O(n)\),假设数组总共有 \(n\) 个元素,\(fast\) 和 \(slow\) 至多遍历 \(n\) 步
- 空间复杂度:\(O(1)\)
原文链接: https://www.cnblogs.com/bky-hbq/p/13171864.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/357559
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!