非零区域三角形的最大周长

Question

给定整数数组num，返回由其中三个长度组成的非零区域的三角形的最大周长。如果不可能形成非零区域的任何三角形，则返回0。

我可以考虑蛮力法，另一种方法是对给定的数组进行排序，向后迭代一个循环，检查形成三角形的条件并返回和，还有其他方法来解决这个问题吗？

Answer 1

我能想到的最佳算法是将数字放入堆中，而不是对数组进行排序。通常是O(n)来创建堆，而O(1)则是查找三角形。最坏的情况是，如果没有数字满足三角形条件，则需要进行O(n log(n))比较。这种最坏的情况只有当你允许大整数进入混合时才能被击中。例如，对于64位整数，最坏的情况是O(n)。

考虑到您必须查看每个元素，您不能比O(n)平均时间做得更好。对于固定大小的整数，所有的技巧，比如基数排序，都不会有多大帮助。

即使在任意整数的情况下，它仍然是非常好的。

假设我们有一个基于比较的算法和最坏的o(n log(n))情况。然后，通过跟踪所做的比较，并将Kahn的算法应用于拓扑排序，您将得到一个基于比较的排序，即o(n log(n))，这是众所周知的不可能的排序。

对于任意大小的整数，我很难找到一个基于非比较的算法，这个算法可能会做得更好。