时间戳

首页 > 解决方案 > N/3 重复次数线性解

algorithm - N/3 重复次数线性解

问题描述

“给定一个包含 n 个整数的只读数组。找出是否有任何整数在线性时间和恒定附加空间中出现超过 n/3 次。如果是，则返回整数。如果不是，则返回 -1。如果有多个解决方案，返回任何一个"

对于上述问题，我有两个答案，其中一个是在线性时间内被接受的。

这个没有被接受（部分接受）TLE

    def repeatedNumber(self, A):
    A=list(A)
    n=len(A)
    b=list(set(A))
    if(len(A)==1 or len(A)==2):
        return A[0]
    if(len(b)==n):
        return(-1)
    for i in range(len(b)):
        if(A.count(b[i])>n//3):
            return b[i]
    return(-1)

此代码正在被接受

    def repeatedNumber(self, A):
    A=list(A)
    n=len(A)
    ck={}
    for i in A:
        if i not in ck:
            ck[i]=1
        else:
            ck[i]+=1
        if(ck[i]>n/3):
            return i
    return(-1)

此代码在线性运行时被接受。虽然 for 循环运行 n 次，但时间复杂度应该是 O(n)。但这在线性时间内执行。谁能解释一下？

标签： algorithmpython-2.7dictionarytime-complexity

解决方案

第二个代码的TC 是 O(n)所以它被接受了。这是 O(n)，因为您使用的是字典，并且为给定键提取值的平均 TC 是常数 O(1)。

第一个代码的 TC 是 O(n^2)而不是 O(n)，因为 Python 中的 count 函数的平均 TC 为 O(n)，并且您在 for 循环中使用它也是 O(n)，因此净 TC是 O(n^2) 这就是为什么它没有被接受

两种解决方案的空间复杂度均为 O(n)。

有人提到你必须在恒定空间而不是线性空间中解决这个问题。
您的两个解决方案都是线性空间。

这里给出了恒定空间和线性时间的解决方案

推荐阅读