寻找时间复杂度为 O(n+k) 的三元组

Question

该函数获取一个非负整数列表，并且它必须找到列表中恰好 3 次的数字。（整数的值在 0 到 k-1 之间），然后用找到的所有三元组创建一个新列表。

我很难理解 O(n+k) 时间复杂度，我选择了，如果 k 大于 n 那么它将是 O(k) 并且相反，并尝试写这个第一种情况的代码 (k>n):

def k_bigger_than_n(lst, k): # a function that works in case k is bigger than n
    triplets = []
    for i in range(int(k+1)):
        count=0
        if (i in lst): # checks if in list first time
            count += 1
            lst.remove(i)
            if (i in lst): # checks if its in list again (2 repetitions)
                count += 1
                lst.remove(i)
                if(i in lst): # checks if theres 3 repetitions of i
                    count+=1
                    lst.remove(i)
                    if(i in lst): #in case theres more than 3 its no longer added to our triplets.
                        count=0
        if(count==3):
            triplets.append(i)
            triplets.append(i)
            triplets.append(i)
    return triplets

我想知道我在 if 语句中使用的 in 是否破坏了我的时间复杂度，或者我是否正确理解 O(n+k) 的时间复杂度。

感谢任何解释，谢谢。

Answer 1

下一个代码将具有 O(n) 复杂度，它使用 dict()。你不能有更少的复杂性，因为你必须至少查看所有元素一次才能找出剩余数字中哪些仍然可以形成三元组。您所能做的就是在 O(n).

中设置更大或更小的常量乘数

Try it online!

def find_triplets(l):
    c = {}
    for e in l:
        c[e] = c.get(e, 0) + 1
    return [k for k, v in c.items() if v == 3]

print(find_triplets([7, 2, 7, 3, 7, 1, 2, 2, 4, 5, 5, 4, 4, 4]))

输出：

[7, 2]

PS。出于好奇，我在 this online snippet although it is not as efficient as O(n) algorithm above. And another O(n log n) algorithm using sorting I implemented here. Also another O(n + k) algorithm using counting-sorting array here online.

中提供了完全 O(n + k) 复杂度的算法

寻找时间复杂度为 O(n+k) 的三元组

finding triplets with O(n+k) time complexity

python

time-complexity