时间戳

首页 > 解决方案 > 有没有办法在 O(n) 时间复杂度中解决这个问题？

python - 有没有办法在 O(n) 时间复杂度中解决这个问题？

问题描述

我有一个元组列表作为输入，如下所示。

input = [(5,6), (6,4), (6,3), (0,5), (1,2), (2,0)]

现在我需要找出在所有元组中哪个元素出现在第一位，但没有出现在元组的第二位。就像在这种情况下我们有“1”。输出将始终是单个值。

为了找到这个，我想出了以下解决方案。

input = [(5,6),(6,4),(6,3),(0,5),(1,2),(2,0)] #input
A = []                                        #to store elements in first position of the tuple
B = []                                        #to store elements in second position of the tuple
for i in input:
    A.append(i[0])
    B.append(i[1])

for i in A:
    if i not in B:
        print (i)

这里，第一个 for 循环运行 n 次，其中 n 是输入中的元组数。因此，时间复杂度为 O(n)。第二个循环也运行 n 次，并且检查元素是否在列表 B 中的 if 语句也需要 O(n) 时间。所以第二个for循环的时间复杂度是O(n^2)。因此，我的解决方案的时间复杂度为 O(n^2)。

有没有办法以线性时间复杂度做到这一点？

谢谢！

标签： pythontime-complexity

解决方案

input = [(5,6),(6,4),(6,3),(0,5),(1,2),(2,0)]
A = set()
B = set()
for ele in input:
    A.add(ele[0])
    B.add(ele[1])

for ele in A:
    if not B.contains(ele):
        return ele

一个集合具有 O(1) 查找时间，因此比较元素将花费 O(n) 而不是 O(n^2)

推荐阅读