perl – 什么是具有低计算复杂度的单线程,用于返回数组的两个最

发布时间：2020-12-16 06:28:52 所属栏目：大数据来源：网络整理

导读：这更像是“我感兴趣,如果它可能”而不是“我真的需要它”的问题,但无论如何：我知道如果我想使用自定义函数比较列表中的最小值,我可以使用List轻松完成::的Util ::减少. my $biggest = reduce {comparison($a,$b) ? $b:$a} @myArray; 但是,如果我想要该阵列

这更像是“我感兴趣,如果它可能”而不是“我真的需要它”的问题,但无论如何：我知道如果我想使用自定义函数比较列表中的最小值,我可以使用List轻松完成::的Util ::减少.

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

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

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

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

但我可能要求太多了:)

解决方法

要查找列表的最大两个值,您可以使用两个变量循环遍历值以保持最大值：

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)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!