题目:
给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
核心思想:考察双指针用法,用两个索引值不同步长的变化来做处理。
双指针执行过程示意图:
flowchart TD A[开始] --> B[i=0, slot=0] B --> C{i < nums.size()?} C -- 是 --> D{nums[i] != val?} D -- 是 --> E[nums[slot] = nums[i]\nslot++] E --> F[i++] D -- 否 --> F F --> C C -- 否 --> G[返回 slot]简要说明:
- i(快指针):遍历整个数组,检查每个元素。
- slot(慢指针):指向下一个可以放置非 val 元素的位置。
- 当
nums[i] != val时,将nums[i]复制到nums[slot],然后slot向前移动一位。 - 当
nums[i] == val时,仅i前进,slot保持不变。 - 遍历结束后,
slot即为新数组的长度,且nums[0..slot-1]均为非 val 元素。
针对本题:
int removeElement(vector<int>& nums, int val) { int slot = 0; // 存储变化后的数组索引 for (int i = 0; i < nums.size(); i++) { if (nums[i] != val) { nums[slot] = nums[i]; slot++; } } return slot; }