algorithm - 在列表中查找升序三元组

Question

我在编程面试中遇到了这个问题，现在还不知道。

A list whose length is n, the elements in it are all positive integers without order. To find out all possible triples (a, b, c), that a < b < c, and a appears before b and b before c in the list.

And analyse the time complexity of your algorithm.

Answer 1

没有任何通用算法可以比 O(n^3) 更快，因为给定不同元素的排序输入，则输出的大小为 O(n^3)，因此仅生成输出所需的时间成正比。事实上，即使是随机生成的整数列表也已经有 n^3 个三元组直到常数因子。

假设您可以按列表顺序简单地遍历所有可能的三元组，并比较它们的排序顺序。这个朴素的解决方案已经是最好的，它可以渐近地(即 O(n^3))

for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        for (int k = j+1; k < n; k++)
            if (X[i] < X[j] && X[j] < X[k)
                output(X[i],X[j],X[k])

我怀疑您的问题陈述中可能存在转录错误 - 或者该问题应该是一个非常简单的简短编码练习。