N*****8
发帖数: 253 | 1 Given a array of positive integers, find all possible triangle triplets that
can be formed from this array.
eg: 9 8 10 7
ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10
Note : array not sorted, there is no limit on the array length
geeks4geeks有类似的，但是只是求三角形个数的，能用n^2事件复杂度解出来。但是如
果求所有的三边的输出，感觉还是要n^3。请教大家的优化方法。 | w****a
发帖数: 710 | | r****7
发帖数: 2282 | 3 要是需要输出所有的话，必然要n^3吧，extreme的case是所有的组合都是valid的，就
必然有n^3个结果啊
that
【在 N*****8 的大作中提到】
: Given a array of positive integers, find all possible triangle triplets that
: can be formed from this array.
: eg: 9 8 10 7
: ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10
: Note : array not sorted, there is no limit on the array length
: geeks4geeks有类似的，但是只是求三角形个数的，能用n^2事件复杂度解出来。但是如
: 果求所有的三边的输出，感觉还是要n^3。请教大家的优化方法。
| N*****8
发帖数: 253 | 4 我觉得也是，最近有个朋友被L问到这道题目，他用N^3解出来了，但是老中主面试官貌
似不满意，所以就有点疑惑了。
【在 r****7 的大作中提到】
: 要是需要输出所有的话，必然要n^3吧，extreme的case是所有的组合都是valid的，就
: 必然有n^3个结果啊
:
: that
| G*********n
发帖数: 53 | 5 sort + two pointer + combination | m*****k
发帖数: 731 | 6 5,4,3,1
可否用这个input示范一下？
【在 G*********n 的大作中提到】
: sort + two pointer + combination
| w****a
发帖数: 710 | |
|
