Leetcode 27. Remove Element: 同一个提交的执行时间差别很大

Question

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. Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length. Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy) int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for (int i = 0; i < len; i++) { print(nums[i]); }

我的回答:

int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) { return 0; }
    int end = nums.size() - 1;
    int curr_val = nums[end];
    for (; end > 0; end--){
        if(curr_val == nums[end - 1]){ // there is duplicate before this value (curr_val)
            nums.erase(nums.begin() + end - 1); // remove the duplicate at the particular index
        } else {
            curr_val = nums[end - 1];
        }
    }

    return nums.size();
}

我的执行时间

同样的答案我提交了five次，执行时间从开始的8ms到4ms，再到0ms。为什么执行时间如此不一致？跟Leetcode平台有关系吗？

Answer 1

LeetCode 并未声称为运行ning 你的程序提供了一个封闭且一致的环境。您可以想象，他们可能有成百上千台运行提交的机器。其中有些可能是五年前买的，有些是全新的，有些暂时运行提交的次数比其他的多，等等。可能有某种相似性机制运行是您第二次提交的第三次在第一次使用的同一台服务器上，可能会避免一些初始化开销。我个人注意到 JavaScript 提交往往运行在第一次提交后更快，即使没有更改。在评估提交的性能时，较少关注绝对运行时间，而更多地关注相对于其他提交的运行时间。如果您正在练习面试，相对的运行时间会告诉您您是否大体上正确地掌握了大 O 算法。如果您比其他提交慢很多，那么您可能使用了错误的方法。在你的情况下，你的运行时间太棒了，所以考虑完成并继续前进！

Leetcode 27. Remove Element: 同一个提交的执行时间差别很大

Leetcode 27. Remove Element: Execution time for the same submission differs drastically

c++

big-o