regex - 如何从只出现一次的列表中获取值？

Question

我在网上看到这个问题。获取列表中仅出现一次的唯一数字，而其他数字在列表中出现两次。数据很大，包含大约一百万个未排序的数字，并且可能包含随机顺序的负数，其中所有数字都出现两次，除了一个数字只出现一次。

my @array = (1,1,2,3,3,4,4)

输出:

2

列表中只有两个不重复。我尝试了我的解决方案。

my $unique;
$unique ^= $_ for(@array);
say $unique;

它不适用于负数但速度很快。

我尝试了一个散列，其中键是数字，值是它在列表中出现的次数。反转散列，然后以 1 作为键打印值，因为所有其他数字都以 2 作为键，因为它们出现了两次。哈希解决方案对于一百万个数字的大量输入很慢，但适用于负数。

我尝试了一种将整个列表与制表符结合起来的正则表达式方式，然后使用

my $combined = join " ", @array;
$combined !~ (\d+).*$1;
say $1;

但我只得到列表的最后一个数字

有没有快速的方法呢？使用正则表达式的任何想法？

编辑:改写标题以获得更好的答案

Answer 1

这看起来相当快:

use v5.10; use strict; use warnings;

sub there_can_be_only_one {
    my @counts;
    $counts[ $_>=0 ? 2*$_ : (-2*$_)-1 ]++ for @{$_[0]};
    $counts[ $_>=0 ? 2*$_ : (-2*$_)-1 ]==1 and return $_ for @{$_[0]};
    return;
}

my @array = (1,1,-4,-4,2,3,-1,3,4,-1,4);
say there_can_be_only_one(\@array);

它基本上是散列技术的一种变体，但使用数组而不是散列。因为我们需要处理负数，所以我们不能在 @counts 数组中原封不动地使用它们。当然，负索引在 Perl 中确实有效，但它们会覆盖我们的正索引数据。失败。

所以我们使用类似于二进制补码的东西。我们在数组中将正数存储为 2*$_，将负数存储为 (-2*$_)-1。即:

Integer:   ... -3  -2  -1   0   1   2   3 ...
Stored as: ...  5   3   1   0   2   4   6 ...

因为这个解决方案不依赖于对列表进行排序，而只是对其进行两次遍历(好吧，平均一次半遍)，它的执行时间为 O(n)对比 Schwern 的 O(n log n) 解决方案。因此对于更大的列表(几百万个整数)应该明显更快。这是我的(相当低功率的)上网本的快速比较:

use v5.10; use strict; use warnings;
use Benchmark qw(timethese);
use Time::Limit '60';

sub tobyink {
    my @counts;
    $counts[ $_>=0 ? 2*$_ : (-2*$_)-1 ]++ for @{$_[0]};
    $counts[ $_>=0 ? 2*$_ : (-2*$_)-1 ]==1 and return $_ for @{$_[0]};
    return;
}

sub schwern {
    my @nums = sort @{$_[0]};
    return $nums[0] if $nums[0] != $nums[1];
    for (1..$#nums-1) {
         my($prev, $this, $next) = @nums[$_-1, $_, $_+1];
         return $this if $prev != $this && $next != $this;
    }
    return $nums[-1] if $nums[-1] != $nums[-2];
}

my @input = (
    1..2_000_000,  # 1_000_001 only appears once
    1..1_000_000, 1_000_002..2_000_000,
);

timethese(1, {
    tobyink  => sub { tobyink(\@input) },
    schwern  => sub { schwern(\@input) },
});

__END__
Benchmark: timing 1 iterations of schwern, tobyink...
schwern: 11 wallclock secs ( 8.72 usr +  0.92 sys =  9.64 CPU) @  0.10/s (n=1)
         (warning: too few iterations for a reliable count)
tobyink:  5 wallclock secs ( 5.01 usr +  0.08 sys =  5.09 CPU) @  0.20/s (n=1)
         (warning: too few iterations for a reliable count)

更新:在我最初的回答中，我错过了任何数字都不会出现超过两次的细节。我假设某些数字有可能出现三次或更多次。使用这个额外的细节，我们可以走得更快:

sub there_can_be_only_one {
    my $tmp;
    $tmp ^= $_>=0 ? 2*$_ : (-2*$_)-1 for @{$_[0]};
    $tmp%2 ? ($tmp+1)/-2 : $tmp/2;
}

say there_can_be_only_one(\@array);

这比我最初的回答快了大约 30%。