是有可能找到为O（n）时间给定阵列中的所有三胞胎？ [英] is it possible to find all the triplets in the given array for the O (n) time?

问题描述

由于数字数组找到所有三胞胎满足给定条件。

Given an array of numbers find all such triplets that satisfy the given condition.

条件： A [1] - ;一个研究[J] LT;一个[K] ，其中 I＆LT; J＆LT;氏/ code>。

Condition: a[i] < a[j] < a[k] where I < j < k.

就可以解决O（n）时间这个问题？

it is possible to solve this problem in O (n) time?

这是不在家工作！

推荐答案

输出（最坏情况）的大小是一个下界复杂

The size of the output (worst case) is a lower bound on the complexity.

由于有可能为O（n ^ 3）这样的三胞胎，复杂性不能为O（n）。

Since there are possibly O(n^3) such triplets, the complexity cannot be O(n).

例如，如果阵列从低到高排序，你将有n个选择3个这样的三胞胎，它是N阶^ 3。

For example if the array is sorted from lowest to highest, you will have n choose 3 such triplets which is order of n^3.

如果这个问题指的是发现三胞胎的数量，这里是最有效的解决方案，我看到：

If the question refers to finding the number of triplets, here is the most efficient solution I saw:

<一个href=\"http://cs.stackexchange.com/questions/7409/count-unique-increasing-subsequences-of-length-3-in-on-log-n\">http://cs.stackexchange.com/questions/7409/count-unique-increasing-subsequences-of-length-3-in-on-log-n

这篇关于是有可能找到为O（n）时间给定阵列中的所有三胞胎？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！