我正在编写 C++ 代码来解决 Leetcode 中的这个问题:https://leetcode.com/problems/remove-element/
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example 1:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length.
我有两个解决方案:
解决方案 A:
int removeElement(vector<int>& nums, int val) {
nums.erase(remove(begin(nums), end(nums), val), end(nums));
return nums.size();
}
解决方案 B:
int removeElement(vector<int>& nums, int val) {
auto it = std::remove(nums.begin(), nums.end(), val);
return it - nums.begin();
}
在我看来,方案B应该比方案A快。然而,结果却恰恰相反:
解决方案 A 花费了 0 毫秒,而解决方案 B 花费了 4 毫秒。
我不知道为什么 remove + erase
比 remove
快。
最佳答案
对于普通可破坏类型的 vector (int
就是这样一种类型),erase(it, end())
通常只是一个 size 成员的减量(或指针成员,取决于实现策略)几乎不需要时间。 4 毫秒是一个非常非常小的差异。它很容易由机器的状态引起。而且我不希望如此小的差异能够重现。
如果你真的想从 vector 中删除元素,请使用第一个版本。如果您真的想做 std::remove
做的事情(您可能不想做),请使用第二个版本。性能不是这里的问题。
关于c++ - 为什么 erase+remove 比 remove 更高效,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57818078/