arrays - 计算可能的“不相同”三角形的数量

Question

我在这里认为相同的是例如一个三角形，例如：3-4-5 和三角形 5-3-4。除了相同的三角形之外，我必须计算可能的三角形的数量。 https://www.geeksforgeeks.org/find-number-of-triangles-possible/ - 我的代码基本上是蛮力方法。我尝试使用 for 从可能的三角形中删除所有相同的三角形，但是使用更大的数组需要很长时间。

我想弄清楚如何更有效地做到这一点，是否可以修改输入数组以使这些相同的三角形甚至不会形成？

标签： arraysc

Answer 1

除非数据集中有重复项，否则您无法获得相同的三角形。

一个建议：您只需要检查两个短边的总和是否大于长边。因此，如果您在开始循环之前对数组进行排序，则只需检查一个组合而不是 3 个。

对它们进行排序后，您可以通过将此条目与此级别的上一个条目进行比较来简化重复检查。所以，if( arr[j] == arr[j-1] ) continue;和if( arr[k] == arr[k-1] ) continue;。你知道 j-1 和 k-1 是有效的索引，因为两个循环都不是从 0 开始的。