leetcode 题号#27 移除元素

查看题目详情可点击此处。

题目

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

示例 1:

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

解题思路

题目中未要求数组元素的输出顺序，所以可以直接遍历数组，当数组元素与val相等时，就将此数组元素与数组末尾元素交换，同时数组的末尾下标前移，直到遍历到数组末尾结束。代码如下：

public static int removeElement(int[] nums, int val) {
  int len = nums.length;
  if(nums.length < 1) {return len;}

    for(int i = 0; i < len; i++) {
      if(nums[i] == val) {
        swap(nums, i, --len);
        i--;
      }
    }

    return len;
}

public static void swap(int[] nums, int beforeIndex, int afterIndex) {
  int temp = nums[afterIndex];
  nums[afterIndex] = nums[beforeIndex];
  nums[beforeIndex] = temp;
}

这样的方式也可以解题，但是不是稳定的算法，数组中的元素因为与数组末尾元素对调后会导致元素前后顺序的混乱。如果要将满足条件，也就是不等于val的数组元素按照未操作前的前后顺序输出，需要调整思路。

可以使用两个指针，一个指针用以遍历数组，一个指针用以标记经操作后的数组的末尾长度，遍历到数组中与val相等的元素，便将相邻且不等于val的元素与标记的数组末尾下标元素交换，数组末尾下标后移，遍历至数组末尾结束。代码如下：

class Solution {
    public int removeElement(int[] nums, int val) {
        int lastIndex = 0;
        int maxIndex = nums.length - 1;
        for(int i = 0; i < maxIndex; i++) {
            if(nums[i] == val && nums[i + 1] == val) {
                continue;
            } else if(nums[i] == val && nums[i + 1] != val) {
                swap(nums, lastIndex, i + 1);
            }
            lastIndex++;
        }
        return lastIndex;
    }
    
    public void swap(int[] nums, int beforeIndex, int afterIndex) {
        int temp = nums[afterIndex];
        nums[afterIndex] = nums[beforeIndex];
        nums[beforeIndex] = temp;
    }
}

这段代码解决方案没问题，但在遇到边界情况时会出现问题，出错情况如下。

输入：
[2]
3
输出：
[]
预期：
[2]

当数组元素只有一个时会便会出现问题，原因在于数组遍历只会遍历到数组末尾的前一位，而此时返回的数组末尾长度仍然是0，导致输出空数组，于是我打算使用哨兵的方式解决，将数组末尾值用val值替换出来，在遍历完之后，再单独对被替换出的数组末尾值判断。

class Solution {
    public int removeElement(int[] nums, int val) {
        int lastIndex = 0;
        if(nums.length < 1) {return lastIndex;}
        
        int maxIndex = nums.length - 1;
        int lastEle = nums[maxIndex];
        nums[maxIndex] = val;
        for(int i = 0; i < maxIndex; i++) {
            if(nums[i] == val && nums[i + 1] == val) {
                continue;
            } else if(nums[i] == val && nums[i + 1] != val) {
                swap(nums, lastIndex, i + 1);
            }
            lastIndex++;
        }

        if(lastEle != val) {
            nums[lastIndex] = lastEle;
            lastIndex++;
        }
        return lastIndex;
    }
    
    public void swap(int[] nums, int beforeIndex, int afterIndex) {
        int temp = nums[afterIndex];
        nums[afterIndex] = nums[beforeIndex];
        nums[beforeIndex] = temp;
    }
}