c++ - 基于值从向量中移除元素的时间复杂度

Question

我正在尝试一个简单的问题，要求我给定一个 std::vector 整数和一个值，从该向量中删除具有该值的所有元素并返回结果向量的大小。我最终写的代码是

int removeElement(vector<int>& nums, int val) {
    for (int i = 0; i < nums.size(); ) {
        if (nums[i] == val) {
            nums.erase(nums.begin() + i);
        } else {
            i++;
        }
    }
    return nums.size();
}

但是，在浏览完我的代码之后，这个解决方案实际上是 O(n^2)，因为我在循环内删除了向量中的元素吗？

标签： c++vector