Re: How to find the N largest values in an array?


"be consistent"
	PerlMonks

Re: How to find the N largest values in an array?

by fundflow (Chaplain)

on Oct 04, 2001 at 14:45 UTC ( [id://116673]=note: print w/replies, xml )

Need Help??

in reply to How to find the N largest values in an array?

The N largest values can be found in O(n) in the following way:

my @list_o_num = qw( 1 22 44 55 63 2 1 2 4 54 8 7 9 2 9 );

print "LIST_O_NUM: @list_o_num \n";

my @l = sort { $a <=> $b } @list_o_num[0..2];

for ( 3 .. $#list_o_num ) {
    my $n = $list_o_num[$_];

    if    ( $n > $l[2] ) { @l = ( $l[1], $l[2], $n ) }
    elsif ( $n > $l[1] ) { @l = ( $l[1], $n, $l[2] ) }
    elsif ( $n > $l[0] ) { @l = ( $n, $l[1], $l[2] ) }
}

print "l: @l \n";
[download]

* to be more precise, this is O(K*n)