如何从vector中仅删除第一个指定值（无则不删）并保证最低时间复杂度？

嗨，这个需求很好解决，而且我们可以轻松做到时间复杂度最优～

核心思路 #

要只删除第一个值为4的元素，我们只需要先定位到第一个4的位置，再删除它就行。这里用std::find是最优选择——它会从容器开头线性遍历，找到第一个匹配元素就立刻停止，时间复杂度是O(k)（k是第一个4所在的位置，最坏情况是O(n)，这已经是理论上的最低成本了，因为你总得找到这个元素才能删除它）。

代码实现 #

// 找到第一个值为4的元素的迭代器
auto it = std::find(ara[2].begin(), ara[2].end(), 4);

// 如果找到该元素（迭代器不等于end()），就执行删除
if (it != ara[2].end()) {
    ara[2].erase(it);
}

为什么这是最优的？ #

• 查找阶段：std::find一旦找到第一个匹配项就停止遍历，不会像std::remove那样遍历整个容器（std::remove是为了删除所有匹配元素设计的），所以在存在第一个4的情况下，查找效率更高。
• 删除阶段：vector的erase操作删除单个元素时，需要移动该元素后面的所有元素，这一步的时间复杂度是O(n - k)，但这是vector的结构特性决定的，不管用什么方法删除中间元素都无法避免这个开销。

对比原代码的区别 #

你的原代码ara[2].erase(std::remove(ara[2].begin(), ara[2].end(), 4), ara[2].end())是利用remove-erase惯用法删除所有匹配元素，而我们现在的方案只定位并删除第一个匹配项，完全符合你的需求，而且在存在第一个匹配项的场景下，比原代码的遍历次数更少。

内容的提问来源于stack exchange，提问作者rosudel