什么是具有低计算复杂度的单线程,用于返回阵列的两个最大值？

Question

这更像是"我感兴趣,如果它可能"而不是"我真的需要它"的问题,但无论如何:我知道如果我想使用自定义函数比较在列表中的最小值,我可以轻松地做到List::Util::reduce.

my $biggest = reduce {comparison($a, $b) ? $b:$a} @myArray;

但是,如果我想要该阵列中的两个最大值？再次,只需一次遍历数组.

我可以通过写一个for循环来做到这一点,但我真的想要一个更加圆润的单行.

---

编辑:通过一次遍历数组,我的意思是计算复杂度不会大于O(n).排序所有文章并不是那么有效,因为我不需要排序所有内容,只需要两个最大的值.

但我可能要求太多了:)

Answer 1

要查找列表中的最大两个值，您可以使用两个变量循环这些值来保存最大值：

my @list = qw(3 1 2 5 9 7 8 6 4);

my ($x, $y) = (0, 0);

($x, $y) = $_ > $x ? ($_, $x) :
           $_ > $y ? ($x, $_) : next for @list;

say "$x $y";  # '9 8'

或者您可以使用折叠来缩小列表：

use List::Util 'reduce';

my $max = reduce {
    $b > $$a[0] ? [$b, $$a[0]] : 
    $b > $$a[1] ? [$$a[0], $b] : $a
} [0, 0], @list;

say "@$max"; # '9 8'

这两个解决方案是等效的，第一个解决方案本质上是程序性的，需要外部状态，第二个解决方案是函数式的，不需要外部状态。第一个可能更快，因为它不创建任何内部阵列用于存储。每个只循环列表一次，所以两者都是O(n)