时间戳

首页 > 解决方案 > leetcode 287 的时间复杂度

arrays - leetcode 287 的时间复杂度

问题描述

如果您访问 leetcode.com/problems/find-the-duplicate-number/solution/（问题 287），则会给出以下解决方案：

def findDuplicate(self, nums):
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)

该解决方案的时间复杂度表示为 O(n)

我试图弄清楚为什么会这样。我的想法是，如果您获得以下列表：

x= [1,2,3,4,5,6,7,8,9,10,11,....98,99,100,100] 即数字不断增加（或不相同）直到重复的数字数组的末尾

然后，当您遍历每个元素时，您需要不断增加的集合大小来查找重复值。这不会比 O(N) 时间长吗？

具体来说，如果您尝试在集合中查找 98，则必须查看 97 (N-4) 个值以查看它不在集合中，然后将其添加。对于 99，您需要查看 98 个值等。它在最坏的情况下似乎是 O(N^2) 解决方案？

标签： arrayspython-3.xlist

解决方案

在某种程度上，你的观点是正确的。举个例子，让要找到的数字是 100。所以，用“for”循环循环将是 O(n)，然后在集合中找到值将是 O(n)/O(1)。

在集合中查找值的平均时间复杂度为 O(1)，而最坏情况的复杂度为 O(n)。在这种情况下，我们有最坏情况的复杂度，因此复杂度为 O(n^2)。

但是，如果您阅读 leetcode 上给出的解决方案，他们会提到“摊销常数时间复杂度”，这意味着可能偶尔会出现最坏的情况。所以他们基本上忽略它并查看平均时间复杂度，结果为 O(1)。

因此时间复杂度为 O(1)。

推荐阅读