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

10 
my %h = map { $ref_array[$_] => $_ } 0 .. $#ref_array;

my @out1 = @ref_array[ sort { $a <=> $b } @h{@in1} ];
my @out2 = @ref_array[ sort { $a <=> $b } @h{@in2} ];

%h持有 key => val 对，如one=> 0、two=>1等。

@h{@in1}是2,0,4经过排序的哈希切片，而数组切片@ref_array[0,2,4]是one, three, five

于 2013-09-20T21:57:25.333 回答
4

这并不复杂。

第 1 步，我们需要将您的值映射到 Perl 可以排序的某个键，例如数字。我们可以使用自定义排序规则数组中元素的索引，例如：

my %custom_value = map { $ref_array[$_] => $_ } 0 .. $#ref_array;

第 2 步，我们使用上述值之一作为键对您的输入进行Schwartzian 变换：

my @out =
  map  { $_->[1] }
  sort { $a->[0] <=> $b->[0] }
  map  {[ $custom_value{$_} => $_ ]}
       @in;
于 2013-09-20T21:58:06.993 回答
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 回答