【LeetCode面试经典150题】27. 移除元素

一、题目

二、思路

三、解法

解法一

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int slow = 0;
        for (int fast = 0; fast < len; fast++) {
            if (nums[fast] != val) {
                int tmp =  nums[slow];
                nums[slow++] = nums[fast];
                nums[fast] = tmp;
            }
        }
        return slow;
    }
}

解析：首先明确两指针的用途，快指针用于遍历数组查找非 val 值，慢指针用于提示其左侧所有元素都应保留，当快指针找到非 val 值后交换两指针所指元素，慢指针往后走一位；

解法二

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int head = 0;
        int tail = len - 1;
        while (head <= tail) {
            if (nums[tail] != val) {
                int tmp = nums[head];
                nums[head++] = nums[tail];
                // 这个地方tail一定不能动！
                // 如果nums[head]不是val的话还要再比较一次
                nums[tail] = tmp;
            } else {
                tail--;
            }
        }
        return head;
    }
}

解析：这里有个要注意的点，为什么返回 head 而不是返回 head + 1 ，这个 head 不是指向数组下标吗？确实是指向数组下标，但是循环终止条件为 head <= tail ，这意味着最后一轮循环时 head 与 tail 会指向同一个元素，并且该元素一定不是 val (这里仔细想想为什么)，于是 head 最后又被加了一次，故这里直接返回 head 即可。

提示：倒数第二轮的情形一定是 slow 指向最后一个非 val 值，而 fast 一定指向最后一个 val 值，所以这轮循环一定进入 else 块，执行 fast--