Featured image of post Remove Element

Remove Element

27. 移除元素

分析

双指针

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

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;
    }
};

时间复杂度

每个元素只遍历一次:O(n)

空间复杂度

O(1)

Built with Hugo
Theme Stack designed by Jimmy