ruby - 如何对数组中最大的两个元素求和

Question

使用 Ruby 获取数组中两个最大值之和的合适方法是什么？

我知道array.sort并且array.max但inject(:+)我不知道如何将它们结合起来。

Answer 1

我强烈赞成更简单和更快的：

array.max(2).reduce(:+)

排序是不必要的，扫描更新大小为 K 的最大堆的数组就足够了。使用Array#max(K)您实现 O(N x log(K)) 的渐近时间复杂度与 O(N x log(N)) 的排序。

Answer 2

[9, 4, 5, 1].sort.last(2).sum
=> 14

Answer 3

[1,2,3,4].sort[-2..-1].inject(:+)

如果您正在寻找一种更有效的解决方案，那么使用这个解决方案会更好：

[1,2,3,4].inject([0, 0]) do |largest, el|
  if largest[0] < el
    largest[1] = largest[0]
    largest[0]  = el
  elsif largest[1] < el
    largest[1] = el
  end
  largest
end.inject(:+)

如果您熟悉算法复杂性，则可以看到第一个是nlognto n^2，具体取决于 Ruby 排序算法，其中第二个解决方案就像n它遍历数组一次一样。

Answer 4

你可以试试这样的

array = [13, 2, 21, 36, 4, 9]

array.reverse.first(2).reduce(:+)

在这种方法中，我们对数组进行反向排序，即从最高到最低排序。这会将最大的数字放在数组的首位。reduce方法返回这些数字的总和。在这种情况下，36 和 21 的和是 57。

57

Answer 5

有一些基准来看看什么是完成某事的最快方法总是好的：

require 'active_support/core_ext/enumerable'
require 'fruity'

ARRAY = (0..1000).to_a.shuffle

compare do

  adriano { ARRAY.max(2).reduce(:+)       }
  mori    { ARRAY.sort.last(2).sum        }
  edgars  { ARRAY.sort[-2..-1].inject(:+) }

end


# >> Running each test 64 times. Test will take about 1 second.
# >> adriano is faster than edgars by 50.0% ± 10.0%
# >> edgars is similar to mori