时间戳

首页 > 解决方案 > 为什么 index 在 python 列表中比 pop 快？

python - 为什么 index 在 python 列表中比 pop 快？

问题描述

您好，我正在对 leetcode 进行编码测试，我有一个问题。

“26. Remove Duplicates from Sorted Array”描述如下。

给定一个排序数组 nums，就地删除重复项，使每个元素只出现一次并返回新长度。不要为另一个数组分配额外的空间，您必须通过使用 O(1) 额外内存就地修改输入数组来做到这一点。

解决方案01

# 4.4948496559999995
idx = 0
for _ in range(len(nums)-1):
    if nums[-1-idx] == nums[-2-idx]:
        nums.pop(-1-idx)
    else:
        idx += 1
return len(nums)

解决方案02

# 3.689027874
ans = 1
for i in range(len(nums)-1):
    if nums[i] != nums[i+1]:
        nums[ans] = nums[i+1]
        ans += 1
return ans

检查时间复杂度

if __name__ == '__main__':
    from timeit import Timer
    t = Timer("for t in [[1, 1, 1, 2], [1, 1, 1, 2, 2, 3], [1, 2, 3, 3, 3, 3], []]: Solution().removeDuplicates(t)", "from __main__ import Solution")
print(t.timeit())

解决方案 01 运行时间为 4.4948496559999995，解决方案 02 运行时间为 3.689027874

pop 和 index 具有 O(1) 时间复杂度，但为什么解决方案 02 比解决方案 01 快？

标签： pythontime-complexity

解决方案

关于 leetcode，我确信的一件事是运行时间不等于算法的时间复杂度。有时这取决于您提交的时间以及网站的繁忙程度。一旦我提交了三次相同的答案，每次都会得到不同的运行时间。

推荐阅读