题目
题目来源leetcode
leetcode地址：27. 移除元素，难度：简单。
题目描述(摘自leetcode)：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。 示例 2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 提示： 0 <= nums.length <= 100 0 <= nums[i] <= 50 0 <= val <= 100
本地调试代码：
class Solution { public int removeElement(int[] nums, int val) { ... } public static void main(String[] args) { Solution solution = new Solution(); int[] arr = new int[]{3,2,2,3}; int arrNums = solution.removeElement2(arr, 3); //打印输出 for (int i=0;i<arrNums;i++) { if(i == 0){ System.out.print("["); } System.out.print(arr[i]); if(i != arrNums-1){ System.out.print(","); }else{ System.out.print("]"); } } } }
题解
No1提交：暴力解法
思路：从左到右遍历整个数组，一旦某个元素等于目标值，那么后面的元素都统一向前面移动，并且对应检测长度-1，待检索位置-1(防止移动到指定覆盖索引位置的元素在下一次校验时校验)，其他见注释。
代码：时间复杂度：O(n^2)
public int removeElement(int[] nums, int val) { int currentLength = nums.length; //初始值设置为数组长度，其会不断变化，实际可表示当前数组中不与val相同的元素数量 for (int i = 0; i < currentLength; i++) { if(nums[i] == val){ for (int j = i+1; j < currentLength; j++) { //整体数组向前移 nums[j-1] = nums[j]; } currentLength--; //由于向前移动，那么最后一个元素及倒数第二个元素重复，没有必要在之后重复进行检测 i--;//由于整体向前移动，那么当前i位置上的元素被原本i位置后的元素覆盖，若是不-1，那么之后会i++，就会在下一次检测时漏掉一个 } } return currentLength; }
No2提交：双指针方式(最优解)
思路：使用一个指针left初始值设为0，同样从左到右遍历一遍数组，若是有不等于val的元素直接存储到数组left的索引下，接着left+1，一有不等于val的就继续重复操作，不断覆盖即可。
相较于之前暴力解法，效率大大提升，这里针对的就是!=val的情况，来对该情况进行统一处理。之前的则是针对于=val情况，整体后面的向前覆盖。
代码：时间复杂度O(n)
public int removeElement(int[] nums, int val) { int left = 0; for (int i = 0; i < nums.length; i++) { if(nums[i] != val){ //一旦有!=val的值，依次存储到索引为left下标中，依次覆盖之前的值即可 nums[left] = nums[i] ; left++; } } return left; }
