Re;

27. Remove Element

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

26. Remove Duplicates from Sorted Array

和上面的27差不多，都是把后面合法元素覆盖到前面来。

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length < 2) return nums.length;

        int ptr = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] != nums[ptr - 1]) nums[ptr++] = nums[i]; 
        }
        return ptr;
    }
}

80. Remove Duplicates from Sorted Array II

和I一个意思，都是ptr和i两个指针的关系判断。

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length < 3) return nums.length;

        int ptr = 2;
        for (int i = 2; i < nums.length; ++i) {
            if (nums[i] == nums[ptr - 1] && nums[i] == nums[ptr - 2]) continue;
            else nums[ptr++] = nums[i];
        }
        return ptr;
    }
}

283. Move Zeros

FB 的超高频

这种写法中，我们调用 swap 的次数取决于从数组第一个 0 开始，后面到底有多少个非 0 元素。

一次 swap = 2次数组写入 + 1次 temp variable 写入，总写入次数为 O(3n)，总数组写入次数为 O(2n)

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;

        int i = 0;
        while (i < nums.length && nums[i] != 0) i++;
        for (int j = i + 1; j < nums.length; ++j) {
            if (nums[j] != 0) swap(nums, i++, j);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

然后 follow-up 肯定是如何减少写入次数 (aka 别用 swap)

这个时候解法就有点像27了，不为目标值的时候（这道题目标值为0），我们把当前值覆盖到前面，从头开始覆盖，不用管被覆盖的值是多少，因为我们只关心最后的结果。

和27不太一样的是，最后要再把0写回去，当然操作是很trivial的。

其实我觉得这个写法才是最直观的，暴力点用 swap 的写法反而 tricky 一点

这种写法中，数组每一个位置一定会被不多不少写入一次，写入次数为 O(n)

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;

        int ptr = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) nums[ptr++] = nums[i];
        }
        for (; ptr < nums.length; ++ptr) nums[ptr] = 0;
    }
}

485. Max Consecutive Ones

public class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int count = 0;
        int result = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == 1) {
                count++;
                result = Math.max(result, count);
            } else count = 0;
        }
        return result;
    }
}

(re)move

Re;