leetcode 287的时间复杂度

2024-05-04 • 问答

如果您访问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）解决方案？

在某种程度上，您的观点是正确的。以一个示例为例，让找到的数字为100。因此，使用“ for”循环进行循环将为O（n），然后在集合中查找值将为O（n）/ O（1）。

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

但是，如果您阅读leetcode给出的解决方案，他们会提到“摊销的恒定时间复杂性”，这意味着有时可能会出现最坏的情况。因此，他们基本上忽略了它，而是查看了平均时间复杂度，得出O（1）。

因此，时间复杂度为O（1）。