去除数组中重复的冗余值

home_king

去除一数组中重复的冗余值，如abbcbde-->abcde，要求时间复杂度及辅助空间复杂度平衡性最好的算法。
分析可知，时间复杂度取决于比较次数C与移动次数M。
两种方案：
方案一.顺序对比法

2. i=1,j=n;                //i向后遍历，j向前遍历
3. while(i<n)
4. {
5.         while (j>i)
6.         {
7.                 if (R[i]==-1 || R[j]==-1) break;
8.                 if (R[j]==R[i]) R[j]=-1;                 //重值的冗余值都赋值为-1
9.                 j--;
10.         }
11.         i++;
12.         j=n;
13. }

复制代码

可得C1(n)
//abbcbde变为a b -1 c -1 d e
//调整数组使之为abcde，略。可得M1(n)
O=C1(n)+M1(n)
辅助空间复杂度为O(0)

方案二.构造一游标数组，把数组“转换”为静态链表，此方案可省去移动调整步骤，但辅助空间复杂度为O(n)

2. R[n]                Cursors[n]
3. a                        0  <-head
4. b                        1       
5. b                        2       
6. c                        3
7. b                        4
8. d                        5
9. e                        6
10. ...                        ...
11. R[n-1]                NULL <-sq
12. 以Cursors索引R，每次比较只调整Cursors。

复制代码

可见难以两全其美，兄弟们有更好的算法，不妨指点。

home

这是CU release兄提供的方法，但unpop()过不了关？

#!/usr/bin/perl -w
use strict;

my @a=('a','b','b','b','c','d') ;
my $t=@a[0];
foreach (@a) {
if ($t==$_) { }
else {
unpop(my @b,$_);
$t=$_;
}
}
my @re=sort(@b);
print "@re\n";

home

有漏洞， 这样会好些。

#!/usr/bin/perl -w
@a=('a','b','b','b','c','d') ;
$t=@a;
foreach (@a) {
if ( $t =! $_ ) {
unpop(@b,$_);
$t=$_;
}
}
if ( @re =! NULL ) {
@re=sort(@b);
}else {
@re=@a; }
print "@re\n";

home_king

Perl处理字符串就是有一手!如此精简，复杂度和C的实现也差不多。
看来，C的索引在Perl里应换成pop操作最合适。

home

请home_king兄把源码写写出来吧？那个unpop不懂得怎么用？

home_king

呵呵，home兄，我对Perl懂得不多，严格来说还未入门。(还是那句话，课业太繁重啦，有空得想你和其他兄弟请教Perl:-)
之所以列出几道算法供兄弟们参考，一是有感Perl语言的高度精炼而又富有创意的表达力，在C领域里能实现的算法，到了这片神秘而又令众多黑客狂热的Perl世界里，是如何描述的呢？我很好奇，也有一种期待；二是欲一窥Perl的效率。
见笑。
要是C源码，我可以给出完整的求精程序。

home

多谢home_king兄的提醒，我也是基础不好阿，学了就忘了些。这是正确的脚本：

#!/usr/bin/perl -w
@a=('a','b','b','b','c','d') ;
($t)=@a;
print "@a \n";
foreach (@a) {
if ( $t ne $_ ) {
push(@b , $_ ) ;
$t = $_;
} }
if ( @re ne NULL ) {
@b=(@b,$a[0]);
@re=sort(@b);
}else {
(@re)=@a; }
print "@re\n";

home

CU的 gunguymadman007兄的脚本也不错。

#!/usr/bin/perl
@frist=(1,2,3,4);@second=(2,3,4,5);
for (@frist){$data{$_}=0;}
for (@second){$data{$_}=0;}
@thrid=sort {$a<=>$b} keys %data;
print "\@frist is @frist\t\t \@second is @second \t\t \@thrid is @thrid\n";
my @aa=('a','b','b','c','b','d','e','f','b','g','e','g','a');
print "primer \@aa is @aa\n";
for (@aa) {$aa{$_}=0;}
my @aa=sort {$a<=>$b} keys %aa;
@bb=sort(@aa);
print @bb,"\n";

home_king

我要好好看看这些Perl源码才行。呵呵。