arrays - 如何打印数组中所有递增索引的三元组？

Question

给定一个数组 ar长度n ，如何打印所有三元组 (ar[i], ar[j], ar[k])优于O(n^3)时间在哪里0<=i<j<=k<n ？

示例输入:

ar[]={5,6,7}

Output:

5 6 6
5 6 7
6 7 7

Answer 1

你不能。

假设数组有n 个元素。输出中包括数组前三分之一、第二个三分之一和第三个三分之一的值的每个组合。右边是 n^3/27 = O(n^3) 输出。

您不能用小于 O(n^3) 的工作产生 O(n^3) 输出。