leetcode 27 [remove val]
改进前
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++)
{
while (nums[i] == val)//考虑到后面移过来的元素可能还是要
//移除的,所以改用循环处理,但是在最后一个如果是目标数,就会陷入死循环
{
size--;
nums[i] += 1;//因为没有想到移动i指针,为了避免移到后面的元素会在最后一轮和最后
//一个元素搞混而陷入死循环。所以,+1就不会一样啦。
for (int j = i; j < size; j++)
nums[j] = nums[j + 1];//0,1,2,2,3,0,4,2
}
}
return size;
}
};
改进后
#include <iostream>
using namespace std;
#include <vector>
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++)
{
if (nums[i] == val)//还是用if判断,不会陷入死循环
{
size--;
i--;//由于后面的数都向前移动了以为,所以在i这个位置还属于没有处理的元素,下一轮还
//要继续处理该位置,但是for循环里i++了,所以这里i--;
//nums[i] += 1;
for (int j = i; j < size; j++)
nums[j] = nums[j + 1];//0,1,2,2,3,0,4,2
}
}
return size;
}
};
int main(void)
{
vector <int> num={ 0,1,2,2,3,0,4,2 };
int target = 2;
Solution s;
cout << s.removeElement(num, target);
return 0;
}
究极改进版——双指针法
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++)
{
if (val != nums[fastIndex])
nums[slowIndex++] = nums[fastIndex];
}
return slowIndex;
}
};