如何在数组中打印所有递增索引的三元组？ [英] How to print all increasing-index triplets in an array?

问题描述

给出长度为 n 的数组 ar ，如何打印所有三元组（ ar [i]，ar [j]，ar [k]）比 O（n ^ 3）时间要好，其中 0< = i< j< = k ？

示例输入：

  ar [] = {5,6,7} 
 
输出：
 
 5 6 6 
 5 6 7 
 6 7 7 
  

解决方案

您可以

假设数组具有 n 个元素。输出中包括数组第一个三分之一，第二个三分之一和第三个三分之一的值的每种组合。右边有 n ^ 3/27 = O（n ^ 3）输出。

您不能产生 O（n ^ 3）输出少于 O（n ^ 3）的工作。

Given an array ar of length n, how can I print all triplets (ar[i], ar[j], ar[k]) in better than O(n^3) time where 0<=i<j<=k<n ?

Example Input:

ar[]={5,6,7}

Output:

5 6 6
5 6 7
6 7 7

解决方案

You can't.

Suppose that the array has n elements. Included in the output is each combination of values from the first third of the array, second third, and third third. That right there is n^3/27 = O(n^3) output.

You cannot produce O(n^3) output with less than O(n^3) work.

这篇关于如何在数组中打印所有递增索引的三元组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！