🍥

Hang Zhang

genius.

Data Structure and Algorithm

Remove Element

27. 移除元素

算法

双指针：

一个读指针（通过范围 for 遍历 nums）
一个写指针 i，用于记录当前应当写入的位置。
每次遇到不等于 val 的元素，就写入当前位置 i 并将 i ++

复杂度分析

时间复杂度：O(n)，每个元素最多被访问一次
空间复杂度：O(1)，只使用了常数额外空间

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution
{
public:
    int removeElement(vector<int>& nums, int val)
    {
        int i = 0; // 写指针
        for (int x : nums)
            if (x != val)
                nums[i ++ ] = x;
        return i;
    }
};

Python 代码

1
2
3
4
5
6
7
8


class Solution:
  def removeElement(self, nums: List[int], val: int) -> int:
    i = 0
    for x in nums:
      if x != val:
        nums[i] = x
        i += 1
    return i

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func removeElement(nums []int, val int) int {
  i := 0
  for _, x := range nums {
    if x != val {
      nums[i] = x
      i ++
    }
  }
  return i
}

JavaScript 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
  let i = 0;
  for (let x of nums) {
    if (x !== val) {
      nums[i++] = x;
    }
  }
  return i;
};