最小成对阵最大和
我有一个整数数组，它的长度是偶数。例如，让{0, 6, 4, 22, 19, 11}使用数组š。把所有的数字配对成对，我必须找到最大的对和。现在，在所有可能的组合中，当对和的最大是最小时，我必须找到这样的情况。在这种情况下，它将是23 (当对是0-22，4-19，6-11)。
现在我能想到的唯一情况是检查每一组可能的对和，找到最大的对，并检查它是否比上一次小。然而，这是令人难以置信的低效率，因为它需要遍历数组的长度和平方次数。我想知道是否有更有效的方法来做到这一点。
我正在考虑排序数组并从第一个和最后一个元素中找到最大和选择对，然后向内移动，但我不确定这在所有情况下是否都是正确的。
回答 1
Stack Overflow用户
发布于 2017-10-05 07:23:52
是的，对所有的案件都是如此！可以用数学来证明！
假设2N数a_1，a_2，a_3，a_4，.，a_2N是不减数(排序后).那么这对是
a_1和a_2N
a_2和a_2N-1
..。
a_N和a_N+1
这些金额的最大值将是最小的。
假设a_i和a_2N+1-i对得到最大值最大值。
然后，我们将改变对，看看我们是否能得到一个较小的最大值。所以a_2N+1-i只能与a_1，a_2，…，a_i-1配对，得到一个较小的最大值，类似地，a_2N+2-i也只能与a_1，a_2，…，a_i-1，……配对，所以对于a_2N。
总之，我们有i数(a_2N+1-i，…，a_2N)必须与i-1数(a_1，a_2，…，a_i-1)成对，这是不可能的。
这样我们就可以得到结论的证明。
我不确定我是否有明确的声明。
最好的运气！
https://stackoverflow.com/questions/46579779
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号