1

给定一个数字数组，找到所有满足给定条件的三元组。

条件：a[i] < a[j] < a[k]在哪里I < j < k。

有可能在 O(n) 时间内解决这个问题吗？

这不是家庭作业！！！

4

1 回答 1

2

输出的大小（最坏情况）是复杂度的下限。

由于可能存在 O(n^3) 个这样的三元组，因此复杂度不可能是 O(n)。

例如，如果数组从最低到最高排序，您将有 n 选择 3 个这样的三元组，即 n^3 的顺序。

如果问题是指查找三元组的数量，这是我看到的最有效的解决方案：

https://cs.stackexchange.com/questions/7409/count-unique-increasing-subsequences-of-length-3-in-on-log-n

于 2014-02-03T16:18:05.457 回答