题目

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

双指针替换 \(O(n)\)

和Remove Duplicates的思路相同，都是维护两个指针。cursor指向我们维护的数组的边界，i一直向前遍历。

[1, 1，1，1, 2, 2, 2, 3]

需要删除所有2。当i找到第一个3，只需要把3复制到cursor指向的位置：第一个2。然后cursor前移，并返回cursor即可。

[1, 1，1，1, 3, 2, 2, 3]

代码

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

结果

银弹！

排序 \(O(n\log_{n})\)

这题双指针的效率已经是\(O(n)\)。排序的\(O(n\log_{n})\)已经没有优势了。