8

可能なすべての要素を含み、英数字の並べ替えとは異なるカスタム順序で並べ替えられた参照配列があります。例えば、

@ref_array = ('one','two','three','four','five','six');

ここで、すべての入力配列を参照配列の順序に基づいてソートする必要があります。入力配列は常に参照配列のサブセットになります。

@in1 = ('three','one','five');  # Input
@out1 = ('one','three','five'); # Desired Output

@in2 = ('six','five','four','three','two','one'); # Input
@out2 = ('one','two','three','four','five','six') # Desired Output
4

4 に答える 4

1

小さい整数キーを使用した並べ替えの場合、基数並べ替えは通常、O(N) の複雑さを備えたより高速なソリューションです。

use Sort::Key::Radix qw(ukeysort);

my @ref = ('one','two','three','four','five','six');
my %ref = map { $ref[$_] => $_ } 0..$#ref;

my @out = ukeysort { $ref{$_} } @in;

または、安価な O(N) カウント ソートを使用することもできます。

my %ref;
$ref{$_}++ for @in;
no warnings 'uninitialized';
my @out = map { ($_) x $ref{$_} } @ref;
于 2013-09-21T05:36:11.650 に答える
0

提示されたすべてのソリューションは、O(NlogN)時間の複雑さによる並べ替えを示しています。実際の並べ替えなしでそれを行う方法があるため、O(N)時間の複雑さがあります。

sub custom_usort {
    my %h;
    @h{@_} = ();
    grep exists $h{$_}, ('one','two','three','four','five','six');
}

編集：

入力に複数の値が存在する可能性がある場合、次の解決策があります。

sub custom_sort {
    my %h;
    $h{$_}++ for @_;
    no warnings 'uninitialized';
    map {($_) x $h{$_}} ('one','two','three','four','five','six');
}
于 2013-09-21T06:56:44.253 に答える