python - O(nlogn) 运行时方法

Question

该函数使用 int 列表并按递增顺序生成列表中的唯一元素。例如:

    singles([4,1,4,17,1]) => [1,4,17]

我只能在O(n^2)的运行时间内完成，想知道如何在不循环的情况下变成O(n)的运行时间。

      def singles(lst):
        if lst==[]: return []
        else:
        rest_fn = list (filter (lambda x: x!=lst[0], lst[1:]))
        return [lst[0]] + singles(rest_fn)

Answer 1

如上所述，根据 https://wiki.python.org/moin/TimeComplexity (引用自 Time complexity of python set operations?，它还链接到更详细的操作列表，sorted 的时间复杂度应该为 O(nlogn)。Set 的时间复杂度应该为 O(n)。因此，执行 sorted(set(input )) 应该有时间复杂度 O(n) + O(nlogn) = O(nlogn)

编辑:如果你不能使用集合，你应该提到这一点，但作为一个提示，假设你可以使用排序，如果你使用双端队列(最差为 O(1)案例插入)。有点像

rez = deque()
last = None
for val in sorted(input):
   if val != last:
      rez.add(val) # or whatever deque uses to add to the end of the list
      last = val