LeetCode.027.Remove Element 从数组中移除指定元素

题目描述

27 Remove Element
https://leetcode-cn.com/problems/remove-element/
https://leetcode.com/problems/remove-element/

Given an array nums and a value val, 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 by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Note that the order of those five elements can be arbitrary.
It doesn't matter what values are set beyond the returned length.

Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

---

解题过程

相似题目
LeetCode.283.Move Zeroes 将数组中的零移到末尾
LeetCode.027.Remove Element 从数组中移除指定元素
LeetCode.026.Remove Duplicates from Sorted Array 删除有序数组中的重复项
LeetCode.080.Remove Duplicates from Sorted Array II 删除有序数组中的重复项2

原地移除数组中指定元素并返回新数组。题目要求不得额外申请新数组，但超过新数组长度的元素不做要求。
看到这道题就想到使用交换和双指针来做，一个指针low从前往后扫描，另一个指针high从后往前扫描，遇到要删除的元素就换到后面去，保证
low之前都是要保留的元素，high之后都是要删除的元素，写起来改了好几遍才改对
时间复杂度 O(n)，空间复杂度 O(1)

SolutionV2018

private static class SolutionV2018 {
    public int removeElement(int[] nums, int val) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            if (val == nums[j]) {
                j--;
            }
            if (val != nums[i]) {
                i++;
            }
            if (i < j && val == nums[i] && val != nums[j]) {
                nums[i] ^= nums[j];
                nums[j] ^= nums[i];
                nums[i++] ^= nums[j--];
            }
        }
        return j + 1;
    }
}

我的方法速度还可以，打败了43%的submission，但比较麻烦，需要单独考虑的情况比较多。

SolutionV2020

边界用例还挺麻烦的，debug改了好几次

private static class SolutionV2020 {
    public int removeElement(int[] nums, int val) {
        if (null == nums || 0 == nums.length) {
            return 0;
        }
        int low = 0, high = nums.length - 1;
        while (low < high) {
            while (nums[high] == val && low < high) {
                high--;
            }
            while (nums[low] != val && low < high) {
                low ++;
            }
            if (low < high) {
                nums[low] = nums[high--];
            }
        }
        return nums[low] == val ? low : low + 1;
    }
}

这道题的Solution中介绍的两种方法非常好，简单且容易理解：

快慢双指针拷贝覆盖

慢指针slow和快指针fast都从前往后扫描，快指针遇到要保留的元素就赋值给慢指针、遇到要删除的元素就跳过，保证慢指针slow之前都是要保留的元素：

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

左右双指针交换

快慢双指针覆盖法的缺点是所有需要保留的元素都要经过一次赋值，遇到删除元素很稀疏的情况效率很低，因为做了大量不必要的赋值操作，所以有了改进版的前后双指针交换法：前指针low从前往后扫描，遇到要删除的元素将其和后指针high交换（实际操作中不需要真正的交换，只需将后指针元素值赋值给前指针，因为超过新数组长度的元素不做要求），由于换过来的后指针元素也可能是要删除的元素，所以发生交换时前指针不后移，下次循环时再判断一遍。

public int removeElement(int[] nums, int val) {
    int i = 0; //前指针
    int n = nums.length; //后指针
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

---

GitHub代码

algorithms/leetcode/leetcode/_027_RemoveElement.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_027_RemoveElement.java

---