LeetCode --- 27.移除元素

LeetCode --- 字符串、数组
简书专栏：https://www.jianshu.com/nb/41796568
知乎专栏：https://zhuanlan.zhihu.com/c_174823416

一、题目描述

来源：力扣（LeetCode）
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
不需要考虑数组中超出新长度后面的元素。

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
不需要考虑数组中超出新长度后面的元素。

要求实现函数public int removeElement(int[] nums, int val){}

二、实现思路及实现

2.1 思路一：双指针法

双指针法在LeetCode 26也使用过，用来处理本题十分适合。定义快慢指针i=0,j=0,使用j作为快指针遍历当前数组，当遇到等于指定元素时，跳过不做处理，当不等于时，令nums[i] = num[j],并令i++,这样当遍历完成时，前k个元素即为去除指定元素剩余的元素，而且相对位置保持不变！！！

public static int removeElement1(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;
    }

2.2 思路二

考虑题目中没有要求的元素顺序，可以使当遍历的元素等于指定元素时，用最后一个元素交换当前的元素。直到元素个数小于等于循环位置。这样做的好处是，当需要移除的元素个数很少时，能够减少基本操作。比如存在一个长度为100的数组，当需要移除的元素仅仅为两个，那么如果按照思路1，比较出不同的，那么基本操作就要执行98次，而用思路二的方法，我们只需要操作2次基本操作即可。一定程度上减少了操作。
当然，如果需要移除的元素较多或者题目要求保证相对位置不变，那么使用第一种方法更为简便

public int removeElement2(int[] nums, int val) {
        int i = 0;
        int n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                n--;
            } else {
                i++;
            }
        }
        return n;
    }

疑问：如果最后一个元素是目标元素，交换到前面会有影响吗？
答：不会，因为交换之后i的值没有变，下一趟循环将会检测nums[i]

三、测试代码

public static void main(String[] args) {
        int[] nums1 = {3, 2, 2, 3};
        System.out.println(removeElement1(nums1, 3));
        System.out.println(Arrays.toString(nums1));
        int[] nums2 = {3, 2, 2, 3};
        System.out.println(removeElement2(nums2, 3));
        System.out.println(Arrays.toString(nums1));

    }

输出结果：

2
[2, 2, 2, 3]
2
[2, 2, 2, 3]