博文中会简要介绍Leetcode P0027题目分析及解题思路。
“Remove Element”比较简单的题目，主要难点在于控制空间复杂度在O(1)。基本思路和上一道题p0026一致。
Given an array nums and a value val, 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 by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
这道题的思路比较直接，时间复杂度是O(n)，使用双指针来做，核心思路是确立双指针的移动条件。我们不难得出以下条件：
令pos是左指针，itr是右指针，一开始pos和itr指向同一个数组元素
当pos指向的不是target时，
pos和itr同时向后移，若itr在数组范围内，赋值nums[pos] = nums[itr]；否则说明数组已经处理完毕，直接返回pos
当pos指向的数是target时，
若itr+1仍在数组范围内，在给nums[pos]赋值nums[itr+1]，向后移动itr；
否则，说明数组已经结束，并且至少最后一个元素是target，直接返回pos
简单来说，没有target的时候，pos和itr指针保持一致，当nums[pos]是target的时候，不断地将nums[itr]赋值给nums[pos]并且向后移动itr，直到nums[pos]不为target。当nums[pos]不为target以后，同时移动pos和itr，将后续的数组向前移动给nums[pos]。
以下是Java的题解代码实现。
class Solution {
public int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0)
return 0;
int pos = 0, itr = 0;
while (itr < nums.length) {
if (nums[pos] == val) {
if (itr+1 < nums.length) {
nums[pos] = nums[itr+1];
++itr;
}
else
return pos;
}
else {
++pos;
++itr;
if (itr < nums.length)
nums[pos] = nums[itr];
else
return pos;
}
}
return pos;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if (nums.size() == 0)
return 0;
int left = 0, right = 0;
while (right < nums.size()) {
if (nums[left] != val) {
++left;
++right;
if (right < nums.size())
nums[left] = nums[right];
else
return left;
}
else {
if (right+1 < nums.size()) {
nums[left] = nums[right+1];
++right;
}
else
return left;
}
}
return left;
}
};