LeetCode 27. 移除元素

我的思路

由于数据是有范围的，则把所有需要删除的数据替换成超出范围的一个数，然后进行排序。（不清楚sort会不会导致空间复杂度不满足要求…)排完之后输出超出范围的数前面的值的个数，如果没有则会一直遍历到vector末尾然后输出个数。个数用的是iter-nums.begin()

代码

class Solution {
    
public:
    int removeElement(vector<int>& nums, int val)
    {
    
        vector<int>::iterator iter; 	// 声明迭代器iter
        //把等于val的值全改成很大的值（如101）
        for(iter = nums.begin(); iter != nums.end(); iter++)
        {
    
	       if (*iter == val)
		    {
    
			    iter =nums.erase(iter);
			    iter = nums.insert(iter,101);
		    }                          
        }
        //排序
        sort(nums.begin(),nums.end());
        
        //返回个数
        
        iter = nums.begin(); 
        while( iter!=nums.end() && (*iter)!=101 ){
    iter++;}
        return iter - nums.begin();
    }
};

标准解法：双指针法

通过这一题学习了快慢指针的思路。本题实际上用的是数组下标。
1 3 2 1 5 2 1
快指针：i不断向后移
慢指针：碰到nums[j]==val时，就跳过；其余时间一直是nums[j]=nums[i]，即快指针所指的位置。
1 3 跳过 1 5 跳过 1

代码

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)
            {
    
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};