1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int ptrNextPlace = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[ptrNextPlace] = nums[i];
                ptrNextPlace += 1;
            }
        }
        return ptrNextPlace;
    }
}

最直接的想法.
时间复杂度: O(n)
空间复杂度: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right -= 1;
            } else {
                left += 1;
            }
        }
        return left;
    }
}

还有一种解法就是swap. 如果left指向的数字是val, 那么把right的数字给到left, left的数字给到right. 当然我们也不一定非要swap, 只用把left指向的值更新成right指向的值即可, 然后更新right, 当然right指向的也可能是val, 于是我们此时不更新left. 直到二者相错, 我们停止. 这样我们知道, right右侧的数字肯定都是val, 只是我们没有实际真把这些位置的数字都变成val, left左侧的数字肯定都不是val. 于是我们就能得出, right此时指向的数字不是val, 因为此时right在left的左侧. left指向的数字是val(我们想象出是val, 实际可能是别的数字), 那么不是val的界限就很明显了. 就是left的左侧, 且不包含left. 那么长度就是left.

时间复杂度: O(n)
空间复杂度: O(1)