LeetCode27 Remove Element

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

样例

1
2
Input:
nums = [3,2,2,3], val = 3
1
2
3
Output:
Your function should return length = 2,
with the first two elements of nums being 2

思路

将数组中所有指定元素移动到数组末尾,且不能使用额外的内存空间。

使用双指针,$i$ 指向当前访问的元素,$j$ 代表之前有出现过多少个非指定元素。将指定元素移到末尾,相当于将其他元素移到前面。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0, j = 0;
while (i < nums.size()) {
if (nums[i] != val) {
swap(nums[i], nums[j]);
j++;
}
i++;
}
return j;
/* 短小精悍的实现
int k = 0;
for (int& x: nums) if (x != val) swap(x, nums[k++]);
return k;
*/

}
};
分享到 评论