27. 移除元素

题目

这道题通过是通过了，但是有很多可以改进的地方：

附上本人第一次写通过的代码：

/*

slow的作用：作为慢指针，职责是找到val所在的位置

quick的作用：作为快指针，职责是找到第一个可以和slow所指的元素互换位置的元素

*/

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        
        if (nums.empty()) return 0;

        int slow = 0, quick = 0;
        int n = nums.size();
        while (quick < n)
        {
            while (slow < n && nums[slow] != val) slow ++ ;
            quick = max(slow, quick);
            while (quick < n && nums[quick] == val) quick ++ ;
            if (slow < n && quick < n)
            {
                int tmp = 0;
                tmp = nums[slow];
                nums[slow] = nums[quick];
                nums[quick] = tmp;                
            }
            slow ++, quick ++;
        }

        return n - (quick - slow);
    }
};

虽然想到了用快慢指针，但是在对细节的处理上不够好，有点带猜的感觉，思路还是不够清晰。

注意不要自作聪明，认为可以把quick初始化成1，觉得quick不用管nums[0]所在的位置，但是如果数组只有一个元素，那么不会进while循环，没达到判断nums[0]是不是val的目的。

分析下为什么是 return n - (quick - slow);

看官方题解

思路很清晰，而且很巧妙

首先是思路一：

总感觉嗅到了点贪心的味道（不太确定hhh）

其中区间 [0,left) 中的元素都不等于 val这句话值得学习，通过左右指针的相关操作来维持一个性质。

然后是思路二：

感觉精髓是针对一个不是val的元素就进行一次移动，然后就到了合适的位置，就不动了，而不是多次移动到一个合适的位置。

官方方法二代码是这样的：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
};

自己改了点发现也可以

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) 
        {
            if (nums[left] == val )
            {
                nums[left] = nums[right];
                right --;
            }
            else left ++ ;
        }

        return left;
    }
};

所以关键点还是在left和right相交的那个位置上，我们要让这个位置的数也要得到判定，即这个位置的数也要进入while循环。

附上一张自己分析的图：