除了 O(n2) 之外还有什么解决方案。我正在考虑遍历每个值然后得到总和
问问题
119 次
2 回答
8
由 2 个最大元素组成的对总和为最大数。只需找到 2 个最大的元素并将它们相加 - 它是O(n)
对于总和最大的一般k元素，您可以使用选择算法找到 k 最大的元素，然后进行第二次迭代 - 将所有大于它的元素相加。
于 2012-04-27T12:27:39.307 回答
3
如果你想得到最大的两个数，你只需要一个循环，这会使算法O(n)不是O(n^2)。
如果您需要更复杂的配对分析对整数执行快速排序O(n log n)，那么您可以选择两个最大的数字，这将是最大的配对和您想要的任何其他配对组合。
于 2012-04-27T12:27:43.037 回答