O（nlogn）运行时间方法

Question

函数使用int的列表，并以递增的顺序生成列表中的唯一元素。例如：

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

我只能在O（n^2）运行时间内完成，并且想知道如何在没有循环的情况下转换为O（n）运行时间。在

^{pr2}$

Answer 1

如上所述，per https://wiki.python.org/moin/TimeComplexity（引自Time complexity of python set operations?，它也链接到更详细的操作列表，排序后应该具有时间复杂度O（nlogn）。集合的时间复杂度应为O（n）。因此，做sorted(set(input))应该具有时间复杂性O（n）+O（nlogn）=O（nlogn）

编辑： 如果您不能使用set，您应该提到这一点，但是作为一个提示，假设您可以使用sorted，那么如果您使用deque（它有O（1）个最坏情况插入），您仍然可以在O（n）中执行拉出uniques。有点像

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