LeetCode27 RemoveElement


LeetCode地址

解题思路01

通过双指针方式，将不等于val的元素移动到数组的前面，定义两个双指针，slow、fast，初始值均为0。

  1. 遍历数组，当nums[fast]不等于val时，将其赋值给nums[slow],并同时将slow和fast指针都向后移动一位.
  2. 当nums[fast]等于val时,只需要将fast指针向后移动一位即可.同时slow也会随着循环的自增+1
  3. 最后返回fast的长度即可

    代码展示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public class ArrayElementRemoval {
        public static int removeElement(int[] nums, int val) {
            int slow = 0; // 慢指针
            for (int fast = 0; fast < nums.length; fast++) {
                if (nums[fast] != val) {
                    nums[slow++] = nums[fast];
                }
            }
            return slow;
        }
    }
    输出结果：
    1
    New length: 2

    复杂度分析

  • 时间复杂度：遍历数组，时间复杂度为 O(n)，其中 n 为数组的长度。
  • 空间复杂度：原地修改输入数组，使用 O(1) 的额外空间。

解题思路02

如果你希望进一步优化算法的性能，可以考虑以下几个方面：

  1. 减少元素复制的次数：目前的实现中，当遇到不等于 val 的元素时，会进行一次元素复制操作。你可以通过判断 slow 和 fast 指针是否指向同一个位置，避免不必要的元素复制。这样可以减少一部分复制操作的次数。
  2. 从数组末尾开始遍历：由于题目要求不需要考虑新长度后面的元素，我们可以考虑从数组末尾开始遍历，将等于 val 的元素交换到数组末尾。这样的话，就可以避免在每次遇到 val 时都进行元素复制操作，从而减少复制操作的次数。

    代码展示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        public int removeElement(int[] nums, int val) {
            int l =0;
            int r=  nums.length;
            while(l < r){
                if(nums[l] == val){
                    nums[l] = nums[r-- - 1 ];
                }else{
                    l++;
                }
            }
            return l;
        }
    }
    当然你还可以这样写
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public static int removeElement(int[] nums, int val) {
          int slow = 0; // 慢指针
          int fast = nums.length - 1; // 快指针

          while (slow <= fast) {
              if (nums[fast] == val) {
                  fast--;
              } else if (nums[slow] == val) {
                  nums[slow] = nums[fast];
                  slow++;
                  fast--;
              } else {
                  slow++;
              }
          }

          return slow;
      }