给定n个数求最小周长三角形
Given n numbers find minimum perimeter triangle
编码竞赛遇到这个问题。只能考虑 O(n^2 log(n)) 解决方案。我想预期的是 O(n log n).
给我n个数，我要找出3个满足三角不等式且和最小的数
我希望这很容易理解。
例如。
10,2,5,1,8,20
答案是 23 = (5+8+10)
最长的边应该是第二长的后继；否则，我们可以缩小最长的，从而缩小周长。现在您可以使用二进制搜索来查找 O(n) 可能性而不是 O(n^2) 的第三方（实际上，如果您从小到大迭代，您甚至不需要搜索，尽管排序会还是要花钱）。
我认为答案是这样的，假设数字中没有重复。
对数字进行排序。然后扫描数字并取第一个小于前两个数字之和的数字。称之为 x(n) 。 . .已排序序列的第 n 个位置。
x(n) 是其中一个数字，到目前为止我们是 O(n log(n)).
然后前面的选择数量有限。那么 x(n-1) 必须是数字之一，因为 x(n-2) + x(n-3) < x(n-1) < x(n)。然后它是一个简单的扫描直到 x(n-1) 以找到匹配的最小数字。这可能是在系列的开头，如 2、3、8、15、16。
我认为分析与重复基本相同。
编码竞赛遇到这个问题。只能考虑 O(n^2 log(n)) 解决方案。我想预期的是 O(n log n).
给我n个数，我要找出3个满足三角不等式且和最小的数
我希望这很容易理解。
例如。 10,2,5,1,8,20
答案是 23 = (5+8+10)
最长的边应该是第二长的后继；否则，我们可以缩小最长的，从而缩小周长。现在您可以使用二进制搜索来查找 O(n) 可能性而不是 O(n^2) 的第三方（实际上，如果您从小到大迭代，您甚至不需要搜索，尽管排序会还是要花钱）。
我认为答案是这样的，假设数字中没有重复。
对数字进行排序。然后扫描数字并取第一个小于前两个数字之和的数字。称之为 x(n) 。 . .已排序序列的第 n 个位置。
x(n) 是其中一个数字，到目前为止我们是 O(n log(n)).
然后前面的选择数量有限。那么 x(n-1) 必须是数字之一，因为 x(n-2) + x(n-3) < x(n-1) < x(n)。然后它是一个简单的扫描直到 x(n-1) 以找到匹配的最小数字。这可能是在系列的开头，如 2、3、8、15、16。
我认为分析与重复基本相同。